Cod sursa(job #542412)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 26 februarie 2011 13:03:24
Problema Gossips Scor 40
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.76 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define sh short int
#define pb push_back
#define minn(a,b) ((a<b)?a:b)
#define NM 100005
int e[19][NM<<1],N,M,Q,x,y,dep[NM],lung,jum,pr[NM],log[NM<<1];
int euler[NM<<1],nr;
int x1[NM],y1[NM],t[NM];
vector<int>arb[NM];
char s[25];
inline int solve(int x, int y)
{
	if (pr[x]>pr[y])
	{
		int aux = x;
		x = y;
		y = aux;
	}
	int dim=1<<log[pr[y]-pr[x]+1];
	int lo=log[pr[y]-pr[x]+1];
	if(dep[e[lo][pr[x]]]<dep[e[lo][pr[y]-dim+1]])
		x=e[lo][pr[x]];
	else
		x=e[lo][pr[y]-dim+1];
	return x;
}
inline bool caut()
{
	int i,rez,xx,yy;
	for (i=1; i<=x1[0]; ++i)
	{
		xx=x;
		yy=x1[i];
		rez=solve(xx,yy);
		if (rez!=xx&&rez!=yy)
			continue;
		
		xx=y;
		yy=y1[i];
		rez=solve(xx,yy);
		
		if (rez!=xx)
			continue;
		return true;
	}
	return false;
}
inline void df(int x)
{
	euler[++nr] = x;
	if (!pr[x])
		pr[x]=nr;
	size_t g=arb[x].size(), y;
	for (size_t i=0; i<g; ++i)
	{
		y = arb[x][i];
		
		dep[y] = dep[x] + 1;
		df(y);
		euler[++nr] = x;
	}
}
inline void rmq()
{
	int i;
	log[2]=1;
	for (i=1;i<=nr;++i)
		e[0][i] = euler[i];
	for(i=3; i<=nr; ++i)
		log[i]=log[i>>1]+1;
	for (int i=1; i<=log[nr]; ++i)
	{
		lung=1<<i;
		jum=lung>>1;
		for(int j=1; j+lung-1<=nr; ++j)
			if(dep[e[i-1][j]]<dep[e[i-1][j+jum]])
				e[i][j]=e[i-1][j];
			else
				e[i][j]=e[i-1][j+jum];
	}
}
inline void pars()
{
	sh i=0;
	while (s[i]>='0'&&s[i]<='9')
	{
		N=N*10+s[i]-'0';
		++i;
	}
	++i;
	while (s[i]>='0'&&s[i]<='9')
	{
		M=M*10+s[i]-'0';
		++i;
	}
	++i;
	while (s[i]>='0'&&s[i]<='9')
	{
		Q=Q*10+s[i]-'0';
		++i;
	}
}
inline void pars1()
{
	sh i=0;x=0;y=0;
	while (s[i]>='0'&&s[i]<='9')
	{
		x=x*10+s[i]-'0';
		++i;
	}
	++i;
	while (s[i]>='0'&&s[i]<='9')
	{
		y=y*10+s[i]-'0';
		++i;
	}
}
inline void pars2()
{
	sh i=0;
	x=0;y=0;M=0;
	while (s[i]>='0'&&s[i]<='9')
	{
		M=M*10+s[i]-'0';
		++i;
	}
	++i;
	while (s[i]>='0'&&s[i]<='9')
	{
		x=x*10+s[i]-'0';
		++i;
	}
	++i;
	while (s[i]>='0'&&s[i]<='9')
	{
		y=y*10+s[i]-'0';
		++i;
	}
}

inline void citire()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	//scanf("%d%d%d",&N,&M,&Q);
	fgets(s,23, stdin);
	pars();
	int i;
	while (M--)
	{
		fgets(s,23, stdin);
		pars1();
		//scanf("%d%d",&x,&y);
		arb[x].pb(y);
		t[y]=x;
	}
	for (i=1; i<=N; ++i)
		if (t[i]==0)
			arb[0].pb(i);
	df(0);
	rmq();
	while (Q--)
	{
		//scanf("%d",&x);
		fgets(s,23, stdin);
		pars2();
		if (M&1)//=1
		{
			//scanf("%d%d",&x,&y);
		if (caut())
			printf("YES\n");
		else
			printf("NO\n");
			continue;
		}
		//scanf("%d%d",&x1[++x1[0]],&y1[++y1[0]]);
		x1[++x1[0]]=x;
		y1[++y1[0]]=y;
	}
}
int main()
{
	citire();
	return 0;
}