Cod sursa(job #542390)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 26 februarie 2011 12:53:33
Problema Gossips Scor 40
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.33 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],cmp[NM],nrc;
vector<int>arb[NM];
/*inline void df(int nod)
{
	vector<int >::iterator it,g;
	g=a[nod].end();
	comp[nod]=nrc;
	for (it=a[nod].begin(); it!=g; ++it)
	{
		if (comp[*it])
			continue;
		dep[*it]=1+dep[nod];
		df(*it);
	}
}
inline bool urc(int i)
{
	while (x!=x1[i]&&x)
	{
		x=t[x];
		if (dep[x]<dep[x1[i]])
			return false;
	}
	if (!x)
		return false;
	if ()
}*/
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)
{
	cmp[x]=nrc;
	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];
		if (x==0)
			++nrc;
		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 citire()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	scanf("%d%d%d",&N,&M,&Q);
	int i;
	while (M--)
	{
		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);
		if (x&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]]);
		
	}
}
int main()
{
	citire();
	return 0;
}