Pagini recente » Cod sursa (job #389066) | Cod sursa (job #784554) | Cod sursa (job #3198006) | Cod sursa (job #2222546) | Cod sursa (job #673005)
Cod sursa(job #673005)
#include<fstream>
#include<vector>
#include<set>
#define maxn 100005
#define pb push_back
using namespace std;
ifstream f("gossips.in");
ofstream g("gossips.out");
int n,m,op,i,x,y,a,b,lim1,lim2,p,tip;
int gr_in[maxn],lEft[maxn],rIght[maxn];
vector<int>G[maxn];
set<int>Arb[4*maxn],Ad[4*maxn];
set<int>::iterator itt;
void dfs ( int nod ){
lEft[nod] = ++p;
for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
dfs(*itt);
}
rIght[nod] = p;
}
void update ( int nod , int st , int dr ){
Arb[nod].insert(y);
if ( a <= st && dr <= b ){
Ad[nod].insert(y);
return ;
}
int mij = (st + dr) >> 1;
int nodst = nod << 1;
int noddr = nodst + 1;
if ( a <= mij ){
update(nodst,st,mij);
}
if ( b > mij ){
update(noddr,mij+1,dr);
}
}
int query ( int nod , int st , int dr ){
int mij = (st + dr) >> 1;
int nodst = nod << 1;
int noddr = nodst + 1;
itt = Ad[nod].lower_bound(lim1);
if ( itt != Ad[nod].end() && (*itt) <= lim2 ){
return 1;
}
itt = Arb[nod].lower_bound(lim1);
if ( itt != Arb[nod].end() && (*itt) <= lim2 ){
if ( a <= st && dr <= b ){
return 1;
}
if ( a <= mij ){
if ( query(nodst,st,mij) )
return 1;
}
if ( b > mij ){
return query(noddr,mij+1,dr);
}
}
return 0;
}
int main () {
f >> n >> m >> op;
for ( i = 1 ; i <= m ; ++i ){
f >> x >> y;
++gr_in[y]; G[x].pb(y);
}
for ( i = 1 ; i <= n ; ++i ){
if ( !gr_in[i] ){
dfs(i);
}
}
for ( int ii = 1 ; ii <= op ; ++ii ){
f >> tip >> x >> y;
if ( tip == 2 ){
a = lEft[x]; b = rIght[x]; y = lEft[y];
update(1,1,n);
}
else{
a = lEft[x]; b = rIght[x]; lim1 = lEft[y]; lim2 = rIght[y];
if ( query(1,1,n) ){
g << "YES\n";
}
else{
g << "NO\n";
}
}
}
f.close();
g.close();
return 0;
}