oj.uz

Submission #81842

# Submission time Handle Problem Language Result Execution time Memory
81842 2018-10-27T07:53:30 Z gs18115 None (KOI16_tree) C++14
36 / 100
 356 ms 66560 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -