Cod sursa(job #1800030)

Utilizator touristGennady Korotkevich tourist Data 7 noiembrie 2016 10:56:05
Problema Gossips Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair <int,int>
#define mp make_pair
#define fi first
#define se second
#define Nmax 100005

using namespace std;

vector <int> L[Nmax];
vector <pii> Q[Nmax];
int n,q,nr,wh[Nmax],cnt[Nmax],poz[Nmax],l,aib[Nmax];
bool bad[Nmax],ans[Nmax];

inline void Dfs(int nod)
{
    cnt[nod]=1; wh[nod]=nr;
    poz[nod]=++l;
    for(auto it : L[nod])
    {
        Dfs(it);
        cnt[nod]+=cnt[it];
    }
}

inline void upd(int p, int val)
{
    for(int i=p;i<=n;i+=(i&(-i))) aib[i]+=val;
}

inline int qry(int p)
{
    int sol=0;
    for(int i=p;i;i-=(i&(-i))) sol+=aib[i];
    return sol;
}

inline int Qry(int x, int y)
{
    return qry(y)-qry(x-1);
}

inline void Solve(int val)
{
    for(auto it : Q[val])
        if(!it.fi)
            upd(poz[it.se],1);
        else
            ans[it.fi]=(Qry(poz[it.se],poz[it.se]+cnt[it.se]-1)>0);

    for(auto it : Q[val])
        if(!it.fi) upd(poz[it.se],-1);
}

int main()
{
    int m,x,y,i,tip,k=0;
    ifstream cin("gossips.in");
    ofstream cout("gossips.out");
    cin>>n>>m>>q;
    while(m--)
    {
        cin>>x>>y;
        L[x].pb(y);
        bad[y]=1;
    }
    for(i=1;i<=n;++i)
        if(!bad[i])
        {
            ++nr;
            Dfs(i);
        }
    for(i=1;i<=q;++i)
    {
        cin>>tip>>x>>y;
        if(tip==1)
            Q[wh[x]].pb(mp(++k,y));
        else
            Q[wh[x]].pb(mp(0,y));
    }
    for(i=1;i<=nr;++i) Solve(i);
    for(i=1;i<=k;++i)
        if(ans[i]) cout<<"YES\n";
        else cout<<"NO\n";
    return 0;
}