2015年3月19日 星期四

2015/03/19 Codeforces 466E. Information Graph

// http://codeforces.com/problemset/problem/466/E
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int clk = 0, cnt = 0;
bool visit[200000];

int in[200000];
int out[200000];

int gt[200000];
int tm[200000];
vector<int> v[200000];
vector<int> qry;

int FA[200000][20];
int mx[200000][20];

int N, M;

bool is_anc(int a, int b)
{
    return in[a] <= in[b] && out[b] <= out[a];
}

void DFS(int O)
{
    in[O] = ++clk;

    for(int t:v[O]) DFS(t);

    out[O] = ++clk;
}

int main()
{
    scanf("%d %d", &N, &M);

    for(int Ni = 1; Ni <= N; Ni++)
        FA[Ni][0] = Ni;

    for(int Mi = 0; Mi < M; Mi++)
    {
        int t;
        scanf("%d", &t);

        if( t == 1 )
        {
            int x, y;
            scanf("%d %d", &x, &y);

            v[y].push_back(x);
            mx[x][0] = Mi;
            FA[x][0] = y;
        }
        if( t == 2 )
        {
            cnt++;
            scanf("%d", &gt[cnt]);
            tm[cnt] = Mi;
        }
        if( t == 3 )
        {
            int x, i;
            scanf("%d %d", &x, &i);

            qry.push_back(x);
            qry.push_back(i);
        }
    }

    for(int Ni = 1; Ni <= N; Ni++)
        if( FA[Ni][0] == Ni ) DFS(Ni);

    for(int i = 1; i < 20; i++)
        for(int Ni = 1; Ni <= N; Ni++)
        {
            FA[Ni][i] = FA[FA[Ni][i-1] ][i-1];
            mx[Ni][i] = max(mx[Ni][i-1], mx[FA[Ni][i-1] ][i-1]);
        }

    for(int qi = 0; qi < qry.size(); qi+=2)
    {
        int x = qry[qi];
        int i = qry[qi+1];

        if( !is_anc(FA[x][19], gt[i]) ) puts("NO");
        else
        {
            int _x = gt[i]; int m = 0;

            for(int j = 19; j >= 0; j--)
            {
                if( !is_anc(FA[_x][j], x) )
                {
                    m = max(m, mx[_x][j]);
                    _x = FA[_x][j];
                }
                if( !j && !is_anc(_x, x) )
                {
                    m = max(m, mx[_x][0]);
                    _x = FA[_x][0];
                }
            }

            if( x != _x || m > tm[i] ) puts("NO");
            else puts("YES");
        }
    }
}

沒有留言:

張貼留言