답안 #31041 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31041	2017-08-05T15:35:29 Z	TAMREF	트리 (KOI16_tree)	C++11	36 / 100	196 ms	65536 KB

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];
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

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.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51592 KB	Output is correct
2	Correct	6 ms	51592 KB	Output is correct
3	Correct	0 ms	51592 KB	Output is correct
4	Correct	0 ms	51592 KB	Output is correct
5	Correct	0 ms	51592 KB	Output is correct
6	Correct	3 ms	51592 KB	Output is correct
7	Correct	0 ms	51592 KB	Output is correct
8	Correct	0 ms	51592 KB	Output is correct
9	Correct	0 ms	51592 KB	Output is correct
10	Correct	0 ms	51592 KB	Output is correct

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51592 KB	Output is correct
2	Correct	6 ms	51592 KB	Output is correct
3	Correct	0 ms	51592 KB	Output is correct
4	Correct	0 ms	51592 KB	Output is correct
5	Correct	0 ms	51592 KB	Output is correct
6	Correct	3 ms	51592 KB	Output is correct
7	Correct	0 ms	51592 KB	Output is correct
8	Correct	0 ms	51592 KB	Output is correct
9	Correct	0 ms	51592 KB	Output is correct
10	Correct	0 ms	51592 KB	Output is correct
11	Correct	3 ms	51592 KB	Output is correct
12	Correct	3 ms	51592 KB	Output is correct
13	Correct	6 ms	51592 KB	Output is correct
14	Correct	6 ms	51592 KB	Output is correct
15	Correct	0 ms	51592 KB	Output is correct
16	Correct	0 ms	51592 KB	Output is correct
17	Correct	0 ms	51592 KB	Output is correct
18	Correct	0 ms	51592 KB	Output is correct
19	Correct	6 ms	51592 KB	Output is correct
20	Correct	6 ms	51592 KB	Output is correct
21	Correct	0 ms	51592 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51592 KB	Output is correct
2	Correct	6 ms	51592 KB	Output is correct
3	Correct	0 ms	51592 KB	Output is correct
4	Correct	0 ms	51592 KB	Output is correct
5	Correct	0 ms	51592 KB	Output is correct
6	Correct	3 ms	51592 KB	Output is correct
7	Correct	0 ms	51592 KB	Output is correct
8	Correct	0 ms	51592 KB	Output is correct
9	Correct	0 ms	51592 KB	Output is correct
10	Correct	0 ms	51592 KB	Output is correct
11	Correct	3 ms	51592 KB	Output is correct
12	Correct	3 ms	51592 KB	Output is correct
13	Correct	6 ms	51592 KB	Output is correct
14	Correct	6 ms	51592 KB	Output is correct
15	Correct	0 ms	51592 KB	Output is correct
16	Correct	0 ms	51592 KB	Output is correct
17	Correct	0 ms	51592 KB	Output is correct
18	Correct	0 ms	51592 KB	Output is correct
19	Correct	6 ms	51592 KB	Output is correct
20	Correct	6 ms	51592 KB	Output is correct
21	Correct	0 ms	51592 KB	Output is correct
22	Correct	163 ms	51592 KB	Output is correct
23	Correct	173 ms	51592 KB	Output is correct
24	Correct	196 ms	51592 KB	Output is correct
25	Correct	163 ms	51592 KB	Output is correct
26	Correct	176 ms	51592 KB	Output is correct
27	Correct	156 ms	51592 KB	Output is correct
28	Correct	183 ms	51592 KB	Output is correct
29	Correct	196 ms	51592 KB	Output is correct
30	Correct	143 ms	51592 KB	Output is correct
31	Correct	176 ms	51592 KB	Output is correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51592 KB	Output is correct
2	Correct	6 ms	51592 KB	Output is correct
3	Correct	0 ms	51592 KB	Output is correct
4	Correct	0 ms	51592 KB	Output is correct
5	Correct	0 ms	51592 KB	Output is correct
6	Correct	3 ms	51592 KB	Output is correct
7	Correct	0 ms	51592 KB	Output is correct
8	Correct	0 ms	51592 KB	Output is correct
9	Correct	0 ms	51592 KB	Output is correct
10	Correct	0 ms	51592 KB	Output is correct
11	Memory limit exceeded	189 ms	65536 KB	Memory limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	51592 KB	Output is correct
2	Correct	6 ms	51592 KB	Output is correct
3	Correct	0 ms	51592 KB	Output is correct
4	Correct	0 ms	51592 KB	Output is correct
5	Correct	0 ms	51592 KB	Output is correct
6	Correct	3 ms	51592 KB	Output is correct
7	Correct	0 ms	51592 KB	Output is correct
8	Correct	0 ms	51592 KB	Output is correct
9	Correct	0 ms	51592 KB	Output is correct
10	Correct	0 ms	51592 KB	Output is correct
11	Correct	3 ms	51592 KB	Output is correct
12	Correct	3 ms	51592 KB	Output is correct
13	Correct	6 ms	51592 KB	Output is correct
14	Correct	6 ms	51592 KB	Output is correct
15	Correct	0 ms	51592 KB	Output is correct
16	Correct	0 ms	51592 KB	Output is correct
17	Correct	0 ms	51592 KB	Output is correct
18	Correct	0 ms	51592 KB	Output is correct
19	Correct	6 ms	51592 KB	Output is correct
20	Correct	6 ms	51592 KB	Output is correct
21	Correct	0 ms	51592 KB	Output is correct
22	Correct	163 ms	51592 KB	Output is correct
23	Correct	173 ms	51592 KB	Output is correct
24	Correct	196 ms	51592 KB	Output is correct
25	Correct	163 ms	51592 KB	Output is correct
26	Correct	176 ms	51592 KB	Output is correct
27	Correct	156 ms	51592 KB	Output is correct
28	Correct	183 ms	51592 KB	Output is correct
29	Correct	196 ms	51592 KB	Output is correct
30	Correct	143 ms	51592 KB	Output is correct
31	Correct	176 ms	51592 KB	Output is correct
32	Memory limit exceeded	189 ms	65536 KB	Memory limit exceeded
33	Halted	0 ms	0 KB	-

답안 #31041

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 13.0 / 13.0

Subtask #3 14.0 / 14.0

Subtask #4 0 / 19.0

Subtask #5 0 / 45.0

Subtask #1
9.0 / 9.0

Subtask #2
13.0 / 13.0

Subtask #3
14.0 / 14.0

Subtask #4
0 / 19.0

Subtask #5
0 / 45.0