Submission #31042

#	Time	Username	Problem	Language	Result	Execution time	Memory
31042		TAMREF	트리 (KOI16_tree)	C++11	100 / 100	929 ms	51424 KiB

tree

#include <bits/stdc++.h>
using namespace std;
const int mx=400005, ms=1049000;
struct Segtree{
    int arr[mx], seg[ms];
    int n, l, r, i, v;
    int _geti(){
        int now=1,s=0,e=n-1;
        while(s<=e){
            if(seg[now]){
                if(s==e) arr[s]=max(arr[s],seg[now]);
                else{
                    seg[now<<1]=max(seg[now<<1],seg[now]);
                    seg[now<<1|1]=max(seg[now<<1|1],seg[now]);
                }
                seg[now]=0;
            }
            if(s==e) return arr[s];
            int m=(s+e)>>1;
            now<<=1;
            i>m?(now|=1,s=m+1):e=m;
        }
    }
    int geti(int _i){
        i=_i;
        return _geti();
    }
    void _upd(int now, int s, int e){
        if(seg[now]){
            if(s==e) arr[s]=max(arr[s],seg[now]);
            else{
                seg[now<<1]=max(seg[now<<1],seg[now]);
                seg[now<<1|1]=max(seg[now<<1|1],seg[now]);
            }
            seg[now]=0;
        }
        if(l>e||s>r) return;
        if(l<=s&&e<=r){
            if(s!=e){
                seg[now<<1]=max(seg[now<<1],v);
                seg[now<<1|1]=max(seg[now<<1|1],v);
            }else{
                arr[s]=max(arr[s],v);
            }
            return;
        }
        int m=(s+e)>>1;
        _upd(now<<1,s,m);
        _upd(now<<1|1,m+1,e);
    }
    void update(int _l, int _r, int _v){
        //printf("update(%d,%d,%d)\n",_l,_r,_v);
        l=_l, r=_r, v=_v;
        _upd(1,0,n-1);
    }
    void debug(){
        for(int i=0;i<n;i++) printf("S.arr[%d]=%d\n",i,arr[i]);
    }
} S;
int n,q;
int dep[mx], dt[mx>>1], ft[mx>>1];
int p[20][mx>>1];
int ti, de;
vector<int> C[mx];
void dfs(int x, int d=0){
    dt[x]=ti++;
    dep[x]=d;
    for(int i=1;1<<i<=d;i++) p[i][x]=p[i-1][p[i-1][x]];
    for(int u : C[x]){
        dfs(u,d+1);
    }
    ft[x]=ti++;
    dep[x]=d;
}
int lca(int u, int v){
    if(dep[u]<dep[v]) swap(u,v);
    int df=dep[u]-dep[v];
    for(int i=0;df;++i){
        if(df&1<<i){
            df^=(1<<i);
            u=p[i][u];
        }
    }
    for(int L=19;L>=0&&(u!=v);--L){
        if(p[L][u]!=p[L][v]) u=p[L][u],v=p[L][v];
    }
    return u==v?u:p[0][u];
}
void init(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        cin>>p[0][i];
        C[p[0][i]].push_back(i);
    }
    dfs(1);
    S.n=n<<1;
}
void query(){
    for(int b,c,d,v,w;q--;){
        cin>>b>>c>>d;
        //printf("lca of (%d,%d)=%d\n",b,c,lca(b,c));
        v=dep[lca(b,c)]>=max(S.geti(dt[b]),S.geti(dt[c]));
        //assert(S.geti(dt[b])==S.geti(ft[b]) && S.geti(dt[c])==S.geti(ft[c]));
        //printf("dep of lca : %d, maxclimb(b)=%d, maxclimb(c)=%d\n",dep[lca(b,c)],S.geti(dt[b]),S.geti(dt[c]));
        //S.debug();
        puts(v?"YES":"NO");
        if(d){
            w=v?b:c;
            S.update(dt[w],ft[w],dep[w]);
        }
    }
}
int main(){
    init();
    //for(int i=1;i<=n;i++,puts("")) for(int j=printf("anc of %d : ",i)*0;j<20;j++) printf("%d ",p[j][i]);
    //for(int i=0;i<S.n;i++) printf("dfs[%d]=%d\n",i,S.arr[i]);
    //for(int i=1;i<=n;i++) printf("node %d - dt : %d, ft : %d, depth : %d\n",i,dt[i],ft[i],dep[i]);
    query();
}

Compilation message (stderr)

tree.cpp: In member function 'int Segtree::_geti()':
tree.cpp:23:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 19 / 19
• Subtask 5: 45 / 45