Pagini recente » Cod sursa (job #2295830) | Cod sursa (job #2699994) | Cod sursa (job #1935926) | Cod sursa (job #106842) | Cod sursa (job #542350)
Cod sursa(job #542350)
# 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;
}