Cod sursa(job #2032077)

Utilizator Bodo171Bogdan Pop Bodo171 Data 4 octombrie 2017 15:12:30
Problema Gossips Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
vector< pair<int,int> > U[nmax],Q[nmax];
vector<int> stk[nmax];
int arb[4*nmax],st[nmax],dr[nmax],ans[nmax],rad[nmax],tip[nmax];
int n,em,q,i,j,S,D,val,loc,timp,mn,k,a,b;
void update(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod]=val;
        return;
    }
    int m=(l+r)/2;
    if(loc<=m) update(2*nod,l,m);
    else update(2*nod+1,m+1,r);
    arb[nod]=min(arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r)
{
    if(S<=l&&r<=D)
    {
        mn=min(mn,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(S<=m) query(2*nod,l,m);
    if(m<D) query(2*nod+1,m+1,r);
}
void dfs1(int x)
{
    st[x]=++k;
    for(int i=0;i<v[x].size();i++)
        dfs1(v[x][i]);
    dr[x]=k;
}
void dfs2(int x)
{
    for(int i=0;i<U[x].size();i++)
    {
        loc=st[U[x][i].first];
        timp=U[x][i].second;
        stk[loc].push_back(min(stk[loc].back(),timp));
        val=stk[loc].back();
        update(1,1,n);
    }
    for(int i=0;i<Q[x].size();i++)
    {
        S=st[Q[x][i].first];
        D=dr[Q[x][i].first];
        timp=Q[x][i].second;
        mn=(1<<30);
        query(1,1,n);
        if(mn<timp) ans[timp]=1;
        else ans[timp]=0;
    }
    for(int i=0;i<v[x].size();i++)
        dfs2(v[x][i]);
    for(int i=0;i<U[x].size();i++)
    {
        loc=st[U[x][i].first];
        timp=U[x][i].second;
        stk[loc].pop_back();
        val=stk[loc].back();
        update(1,1,n);
    }
}
int main()
{
    ifstream f("gossips.in");
    ofstream g("gossips.out");
    f>>n>>em>>q;
    for(i=1;i<=n;i++)
        rad[i]=1;
    for(i=1;i<=4*nmax-2;i++)
        arb[i]=(1<<30);
    for(i=1;i<=em;i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        rad[b]=0;
    }
    for(i=1;i<=n;i++)
        if(rad[i])
          dfs1(i);
    for(i=1;i<=q;i++)
    {
        f>>tip[i]>>a>>b;
        if(tip[i]==1)
        {
            Q[a].push_back({b,i});
        }
        if(tip[i]==2)
        {
            U[a].push_back({b,i});
        }
    }
    for(i=1;i<=n;i++)
        stk[i].push_back((1<<30));
    for(i=1;i<=n;i++)
        if(rad[i])
          dfs2(i);
    for(i=1;i<=q;i++)
        if(tip[i]==1)
    {
        if(ans[i]) g<<"YES\n";
        else g<<"NO\n";
    }
    return 0;
}