General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
41447852 Practice:
Vatinkriv
1017G - 26 GNU C++14 Accepted 217 ms 15416 KB 2018-08-11 04:53:15 2018-08-11 04:53:15
 
 
→ Source
    #include<bits/stdc++.h>

    using namespace std;

    #define fi  first
    #define se  second

    const int   N   = 1e5 + 1;

    typedef pair<int,int>   ii;
    typedef pair<ii,int>    pii;

    vector<int> g[N];

    int st[N], en[N];
    int ar[N], cnt = 0;
    int n, q, p[N];

    void dfs(int u,int dep) {
        st[u] = ++cnt;
        ar[cnt] = dep;
        for(int v : g[u])
            dfs(v,dep + 1);
        en[u] = cnt;
    }

    pii lz[N << 2];
    int it[N << 2];

    pii add(pii a,pii b)    {
        if(a.se >= 0)   return a;
        b.fi.fi = b.fi.fi + a.fi.fi;
        b.fi.se = max(b.fi.se + a.fi.fi,a.fi.se);
        return b;
    }

    void make(int i,int l,int r)    {
        lz[i] = pii(ii(0,0),-1);
        if(l == r)  {
            it[i] = ar[l];
            return;
        }
        int m = (l + r) / 2;
        make(i << 1,l,m);
        make(i << 1 | 1,m + 1,r);
    }
    void push(int i,int l,int r)    {
        if(lz[i] == pii(ii(0,0),-1))
            return;
        if(l != r)  {
            lz[i << 1]     = add(lz[i],lz[i << 1]);
            lz[i << 1 | 1] = add(lz[i],lz[i << 1 | 1]);
        }
        else    {
            if(lz[i].se >= 0)   it[i] = ar[l] - lz[i].se;
            it[i] = max(it[i] + lz[i].fi.fi,lz[i].fi.se);
        }
        lz[i] = pii(ii(0,0),-1);
    }

    void upd(int i,int l,int r,int a,int b, pii t)  {
        push(i,l,r);
        if(l > b || r < a)  return;
        if(a <= l && r <= b)    {
            lz[i] = t;
            push(i,l,r);
            return;
        }
        int m = (l + r) / 2;
        upd(i << 1,l,m,a,b,t);
        upd(i << 1 | 1,m + 1,r,a,b,t);
    }
    int  get(int i,int l,int r,int p)   {
        push(i,l,r);
        if(l > p || r < p)  return 0;
        if(l == r)  return it[i];
        int m = (l + r) / 2;
        return max(get(i << 1,l,m,p),get(i << 1 | 1,m + 1,r,p));
    }

    int main()  {
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);

        cin >> n >> q;

        for(int i = 2 ; i <= n ; ++i)   {
            cin >> p[i];
            g[p[i]].push_back(i);
        }
        dfs(1,1);
        make(1,1,n);

        while(q--)  {
            int t, u;   cin >> t >> u;
            if(t < 3)   {
                pii z;
                if(t == 1)  z = pii(ii(-1,get(1,1,n,st[p[u]])),-1);
                if(t == 2)  z = pii(ii(0,0),ar[st[p[u]]] - get(1,1,n,st[p[u]]));
                upd(1,1,n,st[u],en[u],z);
            }
            else    {
                int val1 = get(1,1,n,st[u]);
                int val2 = get(1,1,n,st[p[u]]);
                if(val1 == val2)    cout << "black\n";
                else                cout << "white\n";
            }
        }
    }
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details