Pagini recente » Cod sursa (job #2373044) | Cod sursa (job #710433) | Cod sursa (job #2562251) | Cod sursa (job #1318925) | Cod sursa (job #542390)
Cod sursa(job #542390)
#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;
}