Pagini recente » Borderou de evaluare (job #3241814) | Borderou de evaluare (job #980922) | Borderou de evaluare (job #1803947) | Borderou de evaluare (job #320253) | Cod sursa (job #542412)
Cod sursa(job #542412)
#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];
vector<int>arb[NM];
char s[25];
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)
{
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];
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 pars()
{
sh i=0;
while (s[i]>='0'&&s[i]<='9')
{
N=N*10+s[i]-'0';
++i;
}
++i;
while (s[i]>='0'&&s[i]<='9')
{
M=M*10+s[i]-'0';
++i;
}
++i;
while (s[i]>='0'&&s[i]<='9')
{
Q=Q*10+s[i]-'0';
++i;
}
}
inline void pars1()
{
sh i=0;x=0;y=0;
while (s[i]>='0'&&s[i]<='9')
{
x=x*10+s[i]-'0';
++i;
}
++i;
while (s[i]>='0'&&s[i]<='9')
{
y=y*10+s[i]-'0';
++i;
}
}
inline void pars2()
{
sh i=0;
x=0;y=0;M=0;
while (s[i]>='0'&&s[i]<='9')
{
M=M*10+s[i]-'0';
++i;
}
++i;
while (s[i]>='0'&&s[i]<='9')
{
x=x*10+s[i]-'0';
++i;
}
++i;
while (s[i]>='0'&&s[i]<='9')
{
y=y*10+s[i]-'0';
++i;
}
}
inline void citire()
{
freopen("gossips.in","r",stdin);
freopen("gossips.out","w",stdout);
//scanf("%d%d%d",&N,&M,&Q);
fgets(s,23, stdin);
pars();
int i;
while (M--)
{
fgets(s,23, stdin);
pars1();
//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);
fgets(s,23, stdin);
pars2();
if (M&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]]);
x1[++x1[0]]=x;
y1[++y1[0]]=y;
}
}
int main()
{
citire();
return 0;
}