Cod sursa(job #542350)

Utilizator loginLogin Iustin Anca login Data 26 februarie 2011 12:13:27
Problema Gossips Scor 20
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 1.55 kb
# include <fstream>
# include <iostream>
# include <vector>
# include <set>
# include <algorithm>
# define DIM 100003
# define pb push_back
# define mp make_pair
using namespace std;
int n, m, q, in[DIM], ngr, gr[DIM], x[DIM], y[DIM], tmp, h[DIM];
vector<int>G[DIM];
struct nod {
	int g, x, y;
	nod(){}
	nod(int G, int X, int Y){
		g=G;x=X;y=Y;}
	friend bool operator < (const nod &a, const nod &b){
		if (a.g<b.g)return 1;
		if (a.g==b.g && h[a.y]>h[b.y])return 1;
		if (a.g==b.g && h[a.y]==h[b.y] && h[a.x]<h[b.x])return 1;
		return 0;
	}
};
set<nod>S[DIM];
ifstream fin ("gossips.in");

void read ()
{
	int a, b;
	fin>>n>>m>>q;
	for(int i=1;i<=m;++i)
	{
		fin>>a>>b;
		++in[b];
		G[a].pb(b);
	}
	h[0]=DIM;
	h[n+1]=-1;
}	

void DF(int k, int q)
{
	gr[k]=ngr;
	x[k]=++tmp;
	for(vector<int>::iterator I=G[k].begin();I!=G[k].end();++I)
	{
		h[*I]=h[k]+1;
		DF(*I,q);
	}
	y[k]=++tmp;
}

int f (int a, int b)
{
	int i, j;
	set<nod>::iterator it;
	nod q=nod(gr[b]-1,0,n-1);
	for(it=upper_bound(S[gr[a]].begin(),S[gr[a]].end(), q);it!=S[gr[a]].end() && it->g==gr[b] && h[it->y]>=h[b];++it)
	{
		i=it->x;
		j=it->y;
		if ((x[j]>=x[b] && y[j]<=y[b]) && ((x[i]<=x[a] && y[i]>=y[a]) || (x[i]>=x[a] && y[i]<=y[a])))
			return 1;
	}
	return 0;
}

void solve ()
{
	for(int i=1;i<=n;++i)
		if (in[i]==0)
		{
			tmp=0;
			++ngr;
			DF(i, ngr);
		}
	freopen("gossips.out", "w", stdout);
	int o, x, y;
	for(;q--;)
	{
		fin>>o>>x>>y;
		if (o==2)
			S[gr[x]].insert(nod(gr[y],x,y));
		else
			if (f(x,y))
				printf("YES\n");
			else
				printf("NO\n");
	}
}

int main ()
{
	read ();
	solve ();
	
	return 0;
}