oj.uz

Submission #58770

# Submission time Handle Problem Language Result Execution time Memory
58770 2018-07-19T09:43:43 Z andy627 None (KOI16_tree) C++17
36 / 100
 647 ms 66560 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
#define ele (1<<18)
#define INF 2e9
using namespace std;

struct node{
    int root=INF;
}sgt[2222222];

vector<int> edge[2222222];

int num_pos=1;
int par[2222222];
pii sub[2222222];
bool is_gone[2222222];

void dfs_num(int v){
    sub[v].ff=num_pos;
    for(int i=0;i<edge[v].size();i++){
        if(is_gone[edge[v][i]]) continue;
        is_gone[edge[v][i]]=1;
        dfs_num(edge[v][i]);
    }
    sub[v].ss=num_pos++;
}

void spread_(int w,int l,int r){
    if(w>=ele) return;
    sgt[w<<1].root=min(sgt[w<<1].root,sgt[w].root);
    sgt[w<<1|1].root=min(sgt[w<<1|1].root,sgt[w].root);
}

void insert_(int w,int l,int r,int s,int e,int g){
    if(s>e) return;
    if(sgt[w].root<g) return;

    spread_(w,l,r);
    if(s==l && e==r){
        sgt[w].root=g;
        return;
    }

    int m=(l+r)>>1;
    if(s<=m) insert_(w<<1,l,m,s,min(m,e),g);
    if(m<e) insert_(w<<1|1,m+1,r,max(s,m+1),e,g);
}

int search_(int w,int l,int r,int p){
    if(l==p && r==p) return sgt[w].root;

    spread_(w,l,r);

    int m=(l+r)>>1;
    if(p<=m) return search_(w<<1,l,m,p);
    return search_(w<<1|1,m+1,r,p);
}

int main(){
    int n,q;

    scanf("%d %d",&n,&q);
    for(int i=2;i<=n;i++){
        scanf("%d",&par[i]);
        edge[par[i]].push_back(i);
        edge[i].push_back(par[i]);
    }

    is_gone[1]=1; dfs_num(1);
    insert_(1,1,ele,1,n,n);

    while(q--){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);

        int root_a=search_(1,1,ele,sub[a].ss);
        int root_b=search_(1,1,ele,sub[b].ss);

        if(c){
            if(root_a==root_b){
                insert_(1,1,ele,sub[a].ff,sub[a].ss,sub[a].ss);
                printf("YES\n");
            }
            else{
                insert_(1,1,ele,sub[b].ff,sub[b].ss,sub[b].ss);
                printf("NO\n");
            }
        }
        else{
            if(root_a==root_b) printf("YES\n");
            else printf("NO\n");
        }
    }

    return 0;
}

Compilation message

tree.cpp: In function 'void dfs_num(int)':
tree.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<edge[v].size();i++){
                 ~^~~~~~~~~~~~~~~
tree.cpp: In function 'int main()':
tree.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~
tree.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&par[i]);
         ~~~~~^~~~~~~~~~~~~~
tree.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 52600 KB Output is correct
2 Correct 61 ms 52840 KB Output is correct
3 Correct 62 ms 52840 KB Output is correct
4 Correct 49 ms 52840 KB Output is correct
5 Correct 49 ms 52920 KB Output is correct
6 Correct 51 ms 52984 KB Output is correct
7 Correct 49 ms 52984 KB Output is correct
8 Correct 60 ms 52984 KB Output is correct
9 Correct 51 ms 52984 KB Output is correct
10 Correct 48 ms 53048 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 52600 KB Output is correct
2 Correct 61 ms 52840 KB Output is correct
3 Correct 62 ms 52840 KB Output is correct
4 Correct 49 ms 52840 KB Output is correct
5 Correct 49 ms 52920 KB Output is correct
6 Correct 51 ms 52984 KB Output is correct
7 Correct 49 ms 52984 KB Output is correct
8 Correct 60 ms 52984 KB Output is correct
9 Correct 51 ms 52984 KB Output is correct
10 Correct 48 ms 53048 KB Output is correct
11 Correct 67 ms 53048 KB Output is correct
12 Correct 63 ms 53048 KB Output is correct
13 Correct 64 ms 53048 KB Output is correct
14 Correct 54 ms 53048 KB Output is correct
15 Correct 47 ms 53052 KB Output is correct
16 Correct 48 ms 53064 KB Output is correct
17 Correct 56 ms 53140 KB Output is correct
18 Correct 55 ms 53140 KB Output is correct
19 Correct 50 ms 53140 KB Output is correct
20 Correct 49 ms 53140 KB Output is correct
21 Correct 56 ms 53144 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 52600 KB Output is correct
2 Correct 61 ms 52840 KB Output is correct
3 Correct 62 ms 52840 KB Output is correct
4 Correct 49 ms 52840 KB Output is correct
5 Correct 49 ms 52920 KB Output is correct
6 Correct 51 ms 52984 KB Output is correct
7 Correct 49 ms 52984 KB Output is correct
8 Correct 60 ms 52984 KB Output is correct
9 Correct 51 ms 52984 KB Output is correct
10 Correct 48 ms 53048 KB Output is correct
11 Correct 67 ms 53048 KB Output is correct
12 Correct 63 ms 53048 KB Output is correct
13 Correct 64 ms 53048 KB Output is correct
14 Correct 54 ms 53048 KB Output is correct
15 Correct 47 ms 53052 KB Output is correct
16 Correct 48 ms 53064 KB Output is correct
17 Correct 56 ms 53140 KB Output is correct
18 Correct 55 ms 53140 KB Output is correct
19 Correct 50 ms 53140 KB Output is correct
20 Correct 49 ms 53140 KB Output is correct
21 Correct 56 ms 53144 KB Output is correct
22 Correct 243 ms 56096 KB Output is correct
23 Correct 340 ms 56712 KB Output is correct
24 Correct 243 ms 56712 KB Output is correct
25 Correct 279 ms 56712 KB Output is correct
26 Correct 240 ms 56712 KB Output is correct
27 Correct 219 ms 56712 KB Output is correct
28 Correct 207 ms 56712 KB Output is correct
29 Correct 221 ms 56712 KB Output is correct
30 Correct 229 ms 56760 KB Output is correct
31 Correct 229 ms 56760 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 52600 KB Output is correct
2 Correct 61 ms 52840 KB Output is correct
3 Correct 62 ms 52840 KB Output is correct
4 Correct 49 ms 52840 KB Output is correct
5 Correct 49 ms 52920 KB Output is correct
6 Correct 51 ms 52984 KB Output is correct
7 Correct 49 ms 52984 KB Output is correct
8 Correct 60 ms 52984 KB Output is correct
9 Correct 51 ms 52984 KB Output is correct
10 Correct 48 ms 53048 KB Output is correct
11 Runtime error 647 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.
12 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 52600 KB Output is correct
2 Correct 61 ms 52840 KB Output is correct
3 Correct 62 ms 52840 KB Output is correct
4 Correct 49 ms 52840 KB Output is correct
5 Correct 49 ms 52920 KB Output is correct
6 Correct 51 ms 52984 KB Output is correct
7 Correct 49 ms 52984 KB Output is correct
8 Correct 60 ms 52984 KB Output is correct
9 Correct 51 ms 52984 KB Output is correct
10 Correct 48 ms 53048 KB Output is correct
11 Correct 67 ms 53048 KB Output is correct
12 Correct 63 ms 53048 KB Output is correct
13 Correct 64 ms 53048 KB Output is correct
14 Correct 54 ms 53048 KB Output is correct
15 Correct 47 ms 53052 KB Output is correct
16 Correct 48 ms 53064 KB Output is correct
17 Correct 56 ms 53140 KB Output is correct
18 Correct 55 ms 53140 KB Output is correct
19 Correct 50 ms 53140 KB Output is correct
20 Correct 49 ms 53140 KB Output is correct
21 Correct 56 ms 53144 KB Output is correct
22 Correct 243 ms 56096 KB Output is correct
23 Correct 340 ms 56712 KB Output is correct
24 Correct 243 ms 56712 KB Output is correct
25 Correct 279 ms 56712 KB Output is correct
26 Correct 240 ms 56712 KB Output is correct
27 Correct 219 ms 56712 KB Output is correct
28 Correct 207 ms 56712 KB Output is correct
29 Correct 221 ms 56712 KB Output is correct
30 Correct 229 ms 56760 KB Output is correct
31 Correct 229 ms 56760 KB Output is correct
32 Runtime error 647 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.
33 Halted 0 ms 0 KB -