General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
246988063 Practice:
cnyzz
1017G - 26 C++17 (GCC 7-32) Wrong answer on test 3 0 ms 10188 KB 2024-02-18 14:54:54 2024-02-18 14:54:54
→ Source
/*
Author: cnyz
世界があたしを拒んでも今 愛の唄 歌わせてくれないかな
*/
#include<bits/stdc++.h>
using namespace std;

using db=double;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
using ull=unsigned long long;

#define fi first
#define se second
#define gc getchar
#define pb emplace_back
#define mkp make_pair
#define push emplace
#define sz(a) (int)a.size()
#define all(p) p.begin(),p.end()
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

void chkmax(int &x,int y) {if(x<y) x=y;}
void chkmin(int &x,int y) {if(x>y) x=y;}
void chkmax(ll &x,ll y) {if(x<y) x=y;}
void chkmin(ll &x,ll y) {if(x>y) x=y;}
int read() { int x; cin>>x; return x; }

const int N=1e5+5,inf=1e9;
int n,q;
struct node { int dat,sum; } e;
node merge(node a,node b) {
    if(a.dat==inf) return b; if(b.dat==inf) return a;
    return (node){max(a.dat+b.sum,b.dat),a.sum+b.sum};
}
struct {
    #define ls p*2
    #define rs p*2+1
    node tr[N*4];
    int cov[N*4],len[N*4];
    void pushup(int p) {
        tr[p]=merge(tr[p*2],tr[p*2+1]);
    }
    void pushcov(int p) {
        cov[p]=1,tr[p].dat=-1,tr[p].sum=-len[p];
    }
    void pushdown(int p) {
        if(cov[p]) pushcov(ls),pushcov(rs),cov[p]=0;
    }
    void build(int p=1,int l=1,int r=n) {
        len[p]=r-l+1,tr[p].dat=-1,tr[p].sum=-len[p];
        if(l==r) { tr[p].dat=-1,tr[p].sum=-1; return; }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void update(int x,int w,int p=1,int l=1,int r=n) {
        if(l==r) { tr[p].dat+=w,tr[p].sum+=w; return; }
        int mid=(l+r)>>1; pushdown(p);
        if(x<=mid) update(x,w,ls,l,mid);
        else update(x,w,rs,mid+1,r);
        pushup(p);
    }
    void cover(int x,int y,int p=1,int l=1,int r=n) {
        if(x<=l&&r<=y) return pushcov(p);
        int mid=(l+r)>>1; pushdown(p);
        if(x<=mid) cover(x,y,ls,l,mid);
        else cover(x,y,rs,mid+1,r);
        pushup(p);
    }
    node query(int x,int y,int p=1,int l=1,int r=n) {
        if(x<=l&&r<=y) return tr[p];
        int mid=(l+r)>>1; pushdown(p);
        if(y<=mid) return query(x,y,ls,l,mid);
        if(x>mid) return query(x,y,rs,mid+1,r);
        return merge(query(x,y,ls,l,mid),query(x,y,rs,mid+1,r));
    }
} T;
vi G[N];
int son[N],siz[N],dep[N],dfn[N],rev[N],fat[N],top[N],dfc;
void dfs(int u) {
    siz[u]=1;
    for(int v:G[u]) {
        dep[v]=dep[u]+1,fat[v]=u,dfs(v),siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
}
void dfs2(int u,int tp) {
    top[u]=tp; dfn[u]=++dfc,rev[dfc]=u;
    if(son[u]) dfs2(son[u],tp);
    for(int v:G[u]) if(v!=son[u]) dfs2(v,v);
}
void cover(int u) { return T.cover(dfn[u],dfn[u]+siz[u]-1); }
void add(int u,int w) { return T.update(dfn[u],w); }
int query(int u) {
    node ret=e;
    while(u) {
        // node tmp=T.query(dfn[top[u]],dfn[u]);
        // cout<<dfn[top[u]]<<" "<<dfn[u]<<" "<<tmp.dat<<" "<<tmp.sum<<"\n";
        ret=merge(T.query(dfn[top[u]],dfn[u]),ret);
        u=fat[top[u]];
    }
    return ret.dat;
}
void solve() {
    e.dat=inf;
    n=read(),q=read();
    FOR(i,2,n) G[read()].pb(i);
    dfs(1),dfs2(1,1);
    T.build();
    FOR(i,1,q) {
        int op=read(),u=read();
        if(op==1) add(u,1);
        if(op==2) {
            int t=query(u);
            cover(u),add(u,-t);
        }
        if(op==3) cout<<(query(u)>=0?"black\n":"white\n");
    }
}

bool Med;
int main() {
    ios::sync_with_stdio(false),cin.tie(0);
    // fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
    int T=1;
    while(T--) solve();
    // fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details