Cod sursa(job #1240630)

Utilizator teoionescuIonescu Teodor teoionescu Data 11 octombrie 2014 19:47:44
Problema Gossips Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.44 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("gossips.in");
ofstream out("gossips.out");
const int Nmax = 100001;
struct quer{
    int p,x,y;
    quer(){}
    quer(int _p,int _x,int _y){p=_p,x=_x,y=_y;}
} q[Nmax];
int T[Nmax],Data[Nmax],Ans[Nmax],K;
int A[4*Nmax];
int N,M,Q;
vector<int> G[Nmax];
int First[Nmax],Last[Nmax],mark[Nmax],Size;
struct list{
    int x,bro;
} L[40*Nmax]; int alloc;
int query(int x){
    int y,R;
    for(R=T[x];R!=T[R];R=T[R]);
    while(x!=R){
        y=T[x];
        T[x]=R;
        x=y;
    }
    return R;
}
int subord(int a,int b){
    if( First[a]<=First[b] && Last[b]<=Last[a] ) return a;
    if( First[b]<=First[a] && Last[a]<=Last[b] ) return b;
    return 0;
}
void unite(int a,int b){
    Data[a]=subord(Data[a],Data[b]);
    T[b]=a;
}
void push(int cur,int nou,int *p){
    if(cur==0) return;
    if( subord( Data[query(L[cur].x)] , Data[query(nou)] ) ){
        unite( query(L[cur].x) , query(nou) );
        *p=L[cur].bro;
        push(L[cur].bro,nou,p);
    }
    push(L[cur].bro,nou,&(L[cur].bro));
}
void Dfs(int x){
    mark[0]++;
    First[x]=++Size;
    for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it) Dfs(*it);
    Last[x]=++Size;
}
void Update(int i,int st,int dr,int a,int b,int &val){
    if(a<=st && dr<=b){
        push(A[i],val,&A[i]);
        L[++alloc].bro=A[i];
        L[alloc].x=val;
        A[i]=alloc;
    }
    else{
        int mij=(st+dr)/2;
        if(b<=mij) Update(2*i,st,mij,a,b,val);
        else if(a>mij) Update(2*i+1,mij+1,dr,a,b,val);
        else{
            Update(2*i,st,mij,a,mij,val);
            Update(2*i+1,mij+1,dr,mij+1,b,val);
        }
    }
}
void update(int a,int b,int val){
    Update(1,1,Size,a,b,val);
}
void Query(int i,int st,int dr,int wh,int val){
    int p=A[i];
    while(p){
        if( subord(Data[query(L[p].x)],val) ) Ans[query(L[p].x)]=1;
        p=L[p].bro;
    }
    if(st<dr){
        int mij=(st+dr)/2;
        if(wh<=mij) Query(2*i,st,mij,wh,val);
        else Query(2*i+1,mij+1,dr,wh,val);
    }
}
void Check(int i,int st,int dr){
    out<<st<<' '<<dr<<' ';
    int p=A[i];
    while(p){
        out<< L[p].x <<' ';
        p=L[p].bro;
    }
    out<<'\n';
    if(st<dr){
        int mij=(st+dr)/2;
        Check(2*i,st,mij);
        Check(2*i+1,mij+1,dr);
    }
}
int main(){
    in>>N>>M>>Q;
    for(int i=1;i<=M;i++){
        int x,y;
        in>>x>>y;
        mark[y]=1;
        G[x].push_back(y);
    }
    for(int i=1;i<=N;i++) if(!mark[i]){
        int many=mark[0];
        Dfs(i);
        many=mark[0]-many;
    }
    for(int i=Q;i>=1;i--){
        int p,x,y;
        in>>p>>x>>y;
        q[i]=quer(p,x,y);
        T[i]=i;
    }
    for(int i=1;i<=Q;i++){
        if(q[i].p==1){
            //Ans[i]=++K;
            K++;
            Data[K]=q[i].x;
            T[K]=K;
            update(First[ q[i].y ],Last[ q[i].y ],K);
        }
        else{
            Query(1,1,Size,First[q[i].y],q[i].x);
            Query(1,1,Size,Last[q[i].y],q[i].x);
        }
    }
    //Check(1,1,Size);out<<'\n';for(int i=1;i<=K;i++) out<<query(i)<<' ';
    for(int i=K;i>=1;i--) out<< ((Ans[query(i)]==1)?"YES":"NO") <<'\n';
    return 0;
}