답안 #81842 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81842	2018-10-27T07:53:30 Z	gs18115	트리 (KOI16_tree)	C++14	36 / 100	356 ms	66560 KB

tree

#include<iostream>
#include<vector>
using namespace std;
const int MAXN=2e5+10;
const int n=524288;
int in[MAXN],out[MAXN],dp[MAXN];
int ecnt;
vector<int>adj[MAXN];
void ET(const int&X,int dep)
{
    in[X]=++ecnt;
    dp[X]=dep++;
    for(const int&i:adj[X])
        ET(i,dep);
    out[X]=++ecnt;
    return;
}
inline int mn(int x,int y)
{
    return dp[x]>dp[y]?x:y;
}
int ST[n*2+10],lz[n*2+10];
int query(int N,int i,int x,int y)
{
    if(x==y)
        return mn(ST[N],lz[N]);
    int l=N<<1;
    int r=l+1;
    if(dp[ST[N]]<dp[lz[N]])
    {
        ST[N]=lz[N];
        lz[l]=mn(lz[l],lz[N]);
        lz[r]=mn(lz[r],lz[N]);
    }
    int mid=x+y>>1;
    if(i>mid)
        return query(r,i,mid+1,y);
    return query(l,i,x,mid);
}
void lazy(int N,int i,int j,int x,int y,int X)
{
    if(j<x||y<i)
        return;
    if(i<=x&&y<=j)
    {
        lz[N]=mn(X,lz[N]);
        return;
    }
    int l=N<<1;
    int r=l+1;
    if(dp[ST[N]]<dp[lz[N]])
    {
        ST[N]=lz[N];
        lz[l]=mn(lz[l],lz[N]);
        lz[r]=mn(lz[r],lz[N]);
    }
    int mid=x+y>>1;
    lazy(l,i,j,x,mid,X);
    lazy(r,i,j,mid+1,y,X);
    return;
}
inline int MC(int X)
{
    return query(1,in[X],0,n-1);
}
inline void cut(int X)
{
    lazy(1,in[X],out[X],0,n-1,X);
    return;
}
int N,Q,i;
bool flag;
int A,B,C;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>Q;
    for(i=1;i<N;i++)
    {
        cin>>A;
        adj[A-1].push_back(i);
    }
    ET(0,0);
    while(Q-->0)
    {
        cin>>A>>B>>C;
        flag=MC(--A)==MC(--B);
        cout<<(flag?"YES":"NO")<<'\n';
        if(C==1)
            cut(flag?A:B);
    }
    cout<<endl;
    return 0;
}

Compilation message

tree.cpp: In function 'int query(int, int, int, int)':
tree.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=x+y>>1;
             ~^~
tree.cpp: In function 'void lazy(int, int, int, int, int, int)':
tree.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=x+y>>1;
             ~^~

Subtask #1
9.0 / 9.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5240 KB	Output is correct
2	Correct	7 ms	5508 KB	Output is correct
3	Correct	7 ms	5556 KB	Output is correct
4	Correct	7 ms	5620 KB	Output is correct
5	Correct	8 ms	5620 KB	Output is correct
6	Correct	7 ms	5708 KB	Output is correct
7	Correct	7 ms	5708 KB	Output is correct
8	Correct	7 ms	5708 KB	Output is correct
9	Correct	7 ms	5708 KB	Output is correct
10	Correct	7 ms	5708 KB	Output is correct
11	Correct	7 ms	5816 KB	Output is correct
12	Correct	7 ms	5816 KB	Output is correct
13	Correct	6 ms	5816 KB	Output is correct
14	Correct	7 ms	5816 KB	Output is correct
15	Correct	8 ms	5816 KB	Output is correct
16	Correct	7 ms	5816 KB	Output is correct
17	Correct	7 ms	5900 KB	Output is correct
18	Correct	7 ms	5900 KB	Output is correct
19	Correct	7 ms	5900 KB	Output is correct
20	Correct	7 ms	5900 KB	Output is correct
21	Correct	7 ms	5900 KB	Output is correct
22	Correct	137 ms	8720 KB	Output is correct
23	Correct	138 ms	11060 KB	Output is correct
24	Correct	138 ms	13316 KB	Output is correct
25	Correct	137 ms	15380 KB	Output is correct
26	Correct	136 ms	17596 KB	Output is correct
27	Correct	126 ms	19936 KB	Output is correct
28	Correct	126 ms	22256 KB	Output is correct
29	Correct	127 ms	24400 KB	Output is correct
30	Correct	114 ms	26600 KB	Output is correct
31	Correct	128 ms	28820 KB	Output is correct

Subtask #4
0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5240 KB	Output is correct
2	Correct	7 ms	5508 KB	Output is correct
3	Correct	7 ms	5556 KB	Output is correct
4	Correct	7 ms	5620 KB	Output is correct
5	Correct	8 ms	5620 KB	Output is correct
6	Correct	7 ms	5708 KB	Output is correct
7	Correct	7 ms	5708 KB	Output is correct
8	Correct	7 ms	5708 KB	Output is correct
9	Correct	7 ms	5708 KB	Output is correct
10	Correct	7 ms	5708 KB	Output is correct
11	Correct	338 ms	55592 KB	Output is correct
12	Correct	337 ms	59740 KB	Output is correct
13	Correct	356 ms	64068 KB	Output is correct
14	Runtime error	354 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
15	Halted	0 ms	0 KB	-

Subtask #5
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	5240 KB	Output is correct
2	Correct	7 ms	5508 KB	Output is correct
3	Correct	7 ms	5556 KB	Output is correct
4	Correct	7 ms	5620 KB	Output is correct
5	Correct	8 ms	5620 KB	Output is correct
6	Correct	7 ms	5708 KB	Output is correct
7	Correct	7 ms	5708 KB	Output is correct
8	Correct	7 ms	5708 KB	Output is correct
9	Correct	7 ms	5708 KB	Output is correct
10	Correct	7 ms	5708 KB	Output is correct
11	Correct	7 ms	5816 KB	Output is correct
12	Correct	7 ms	5816 KB	Output is correct
13	Correct	6 ms	5816 KB	Output is correct
14	Correct	7 ms	5816 KB	Output is correct
15	Correct	8 ms	5816 KB	Output is correct
16	Correct	7 ms	5816 KB	Output is correct
17	Correct	7 ms	5900 KB	Output is correct
18	Correct	7 ms	5900 KB	Output is correct
19	Correct	7 ms	5900 KB	Output is correct
20	Correct	7 ms	5900 KB	Output is correct
21	Correct	7 ms	5900 KB	Output is correct
22	Correct	137 ms	8720 KB	Output is correct
23	Correct	138 ms	11060 KB	Output is correct
24	Correct	138 ms	13316 KB	Output is correct
25	Correct	137 ms	15380 KB	Output is correct
26	Correct	136 ms	17596 KB	Output is correct
27	Correct	126 ms	19936 KB	Output is correct
28	Correct	126 ms	22256 KB	Output is correct
29	Correct	127 ms	24400 KB	Output is correct
30	Correct	114 ms	26600 KB	Output is correct
31	Correct	128 ms	28820 KB	Output is correct
32	Correct	338 ms	55592 KB	Output is correct
33	Correct	337 ms	59740 KB	Output is correct
34	Correct	356 ms	64068 KB	Output is correct
35	Runtime error	354 ms	66560 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
36	Halted	0 ms	0 KB	-

답안 #81842

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