Cod sursa(job #546302)

Utilizator indestructiblecont de teste indestructible Data 4 martie 2011 19:00:34
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 100005
#define mp make_pair
#define pii pair <int,int>
#define pb push_back
#define f first
#define s second
using namespace std;
int n,m,q,r,dad[NMAX],inc[NMAX],sf[NMAX],nrc,which[NMAX];
vector <int> A[NMAX],aib[NMAX];
vector <pii> C[NMAX];
char viz[NMAX];
struct query{int tip,a,b;};
query B[NMAX];
void read()
{
	scanf("%d%d%d",&n,&m,&q);
	int i,x,y;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&x,&y);
		A[x].pb(y);
		dad[y]=x;
	}
}
void dfs(int nod)
{
	viz[nod]=1;
	inc[nod]=++r;
	which[nod]=nrc;
	int i,vec;
	for (i=0; i<A[nod].size(); i++)
	{
		vec=A[nod][i];
		dfs(vec);
	}
	sf[nod]=++r;
}
void prep()
{
	int i;
	for (i=1; i<=n; i++)
		if (!dad[i])
			nrc++,r=0,dfs(i);
}
int cb(int v1,int v2,int val)
{
	int i,step;
	for (step=1; step<=C[v1].size(); step<<=1);
	for (i=-1; step; step>>=1)
		if (i+step<C[v1].size() && (C[v1][i+step].f<v2 || (C[v1][i+step].f==v2 && C[v1][i+step].s<=val)))
			i+=step;
	return ++i;
}
int lsb(int x)
{
	return x & -x;
}
void update(int v1,int poz,int val)
{
	int i;
	for (i=poz; i<aib[v1].size(); i+=lsb(i))
		aib[v1][i]+=val;
}
int suma(int v1,int poz)
{
	int i,s=0;
	for (i=poz; i>0; i-=lsb(i))
		s+=aib[v1][i];
	return s;
}
void solve()
{
	int i,grup1,grup2,poz,val,poz2;
	for (i=1; i<=q; i++)
	{
		scanf("%d%d%d",&B[i].tip,&B[i].a,&B[i].b);
		if (B[i].tip==2)
		{
			grup1=which[B[i].b]; grup2=which[B[i].a];
			C[grup1].pb(mp(grup2,inc[B[i].b]));
			C[grup1].pb(mp(grup2,sf[B[i].b]));
			aib[grup1].pb(0);
		}
	}
	for (i=1; i<=nrc; i++)
	{
		aib[i].pb(0);
		sort(C[i].begin(),C[i].end());
	}
	for (i=1; i<=q; i++)
	{
		if (B[i].tip==2)
		{
			grup1=which[B[i].b]; grup2=which[B[i].a];
			poz=cb(grup1,grup2,inc[B[i].b]);
			update(grup1,poz,1);
			poz=cb(grup1,grup2,sf[B[i].b]);
			update(grup1,poz,-1);
		}
		if (B[i].tip==1)
		{
			grup1=which[B[i].b]; grup2=which[B[i].a];
			poz=cb(grup1,grup2,inc[B[i].b]-1);
			poz2=cb(grup1,grup2,sf[B[i].b]-1);
			val=suma(grup1,poz2)-suma(grup1,poz);
			if (val>0)
				printf("YES\n");
			else
				printf("NO\n");
		}
	}
}
int main()
{
	freopen("gossips.in","r",stdin);
	freopen("gossips.out","w",stdout);
	read();
	prep();
	solve();
	return 0;
}