oj.uz

Submission #58769

# Submission time Handle Problem Language Result Execution time Memory
58769 2018-07-19T09:41:20 Z andy627 None (KOI16_tree) C++17
55 / 100
 577 ms 65840 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[ele<<1];

vector<int> edge[ele<<1];

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

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 17 ms 12792 KB Output is correct
2 Correct 17 ms 12872 KB Output is correct
3 Correct 15 ms 12872 KB Output is correct
4 Correct 18 ms 12920 KB Output is correct
5 Correct 21 ms 12940 KB Output is correct
6 Correct 18 ms 13004 KB Output is correct
7 Correct 16 ms 13148 KB Output is correct
8 Correct 19 ms 13148 KB Output is correct
9 Correct 18 ms 13148 KB Output is correct
10 Correct 16 ms 13148 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12792 KB Output is correct
2 Correct 17 ms 12872 KB Output is correct
3 Correct 15 ms 12872 KB Output is correct
4 Correct 18 ms 12920 KB Output is correct
5 Correct 21 ms 12940 KB Output is correct
6 Correct 18 ms 13004 KB Output is correct
7 Correct 16 ms 13148 KB Output is correct
8 Correct 19 ms 13148 KB Output is correct
9 Correct 18 ms 13148 KB Output is correct
10 Correct 16 ms 13148 KB Output is correct
11 Correct 17 ms 13148 KB Output is correct
12 Correct 16 ms 13176 KB Output is correct
13 Correct 17 ms 13176 KB Output is correct
14 Correct 16 ms 13208 KB Output is correct
15 Correct 15 ms 13208 KB Output is correct
16 Correct 15 ms 13264 KB Output is correct
17 Correct 16 ms 13280 KB Output is correct
18 Correct 20 ms 13280 KB Output is correct
19 Correct 17 ms 13312 KB Output is correct
20 Correct 19 ms 13328 KB Output is correct
21 Correct 18 ms 13344 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12792 KB Output is correct
2 Correct 17 ms 12872 KB Output is correct
3 Correct 15 ms 12872 KB Output is correct
4 Correct 18 ms 12920 KB Output is correct
5 Correct 21 ms 12940 KB Output is correct
6 Correct 18 ms 13004 KB Output is correct
7 Correct 16 ms 13148 KB Output is correct
8 Correct 19 ms 13148 KB Output is correct
9 Correct 18 ms 13148 KB Output is correct
10 Correct 16 ms 13148 KB Output is correct
11 Correct 17 ms 13148 KB Output is correct
12 Correct 16 ms 13176 KB Output is correct
13 Correct 17 ms 13176 KB Output is correct
14 Correct 16 ms 13208 KB Output is correct
15 Correct 15 ms 13208 KB Output is correct
16 Correct 15 ms 13264 KB Output is correct
17 Correct 16 ms 13280 KB Output is correct
18 Correct 20 ms 13280 KB Output is correct
19 Correct 17 ms 13312 KB Output is correct
20 Correct 19 ms 13328 KB Output is correct
21 Correct 18 ms 13344 KB Output is correct
22 Correct 193 ms 14768 KB Output is correct
23 Correct 219 ms 14872 KB Output is correct
24 Correct 299 ms 14872 KB Output is correct
25 Correct 223 ms 14872 KB Output is correct
26 Correct 215 ms 14872 KB Output is correct
27 Correct 210 ms 14920 KB Output is correct
28 Correct 187 ms 14920 KB Output is correct
29 Correct 214 ms 14920 KB Output is correct
30 Correct 199 ms 14920 KB Output is correct
31 Correct 189 ms 14980 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12792 KB Output is correct
2 Correct 17 ms 12872 KB Output is correct
3 Correct 15 ms 12872 KB Output is correct
4 Correct 18 ms 12920 KB Output is correct
5 Correct 21 ms 12940 KB Output is correct
6 Correct 18 ms 13004 KB Output is correct
7 Correct 16 ms 13148 KB Output is correct
8 Correct 19 ms 13148 KB Output is correct
9 Correct 18 ms 13148 KB Output is correct
10 Correct 16 ms 13148 KB Output is correct
11 Correct 577 ms 31320 KB Output is correct
12 Correct 470 ms 31320 KB Output is correct
13 Correct 525 ms 31492 KB Output is correct
14 Correct 501 ms 31492 KB Output is correct
15 Correct 453 ms 31512 KB Output is correct
16 Correct 495 ms 35540 KB Output is correct
17 Correct 453 ms 40288 KB Output is correct
18 Correct 570 ms 44852 KB Output is correct
19 Correct 456 ms 49360 KB Output is correct
20 Correct 459 ms 52176 KB Output is correct
21 Correct 520 ms 52176 KB Output is correct

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12792 KB Output is correct
2 Correct 17 ms 12872 KB Output is correct
3 Correct 15 ms 12872 KB Output is correct
4 Correct 18 ms 12920 KB Output is correct
5 Correct 21 ms 12940 KB Output is correct
6 Correct 18 ms 13004 KB Output is correct
7 Correct 16 ms 13148 KB Output is correct
8 Correct 19 ms 13148 KB Output is correct
9 Correct 18 ms 13148 KB Output is correct
10 Correct 16 ms 13148 KB Output is correct
11 Correct 17 ms 13148 KB Output is correct
12 Correct 16 ms 13176 KB Output is correct
13 Correct 17 ms 13176 KB Output is correct
14 Correct 16 ms 13208 KB Output is correct
15 Correct 15 ms 13208 KB Output is correct
16 Correct 15 ms 13264 KB Output is correct
17 Correct 16 ms 13280 KB Output is correct
18 Correct 20 ms 13280 KB Output is correct
19 Correct 17 ms 13312 KB Output is correct
20 Correct 19 ms 13328 KB Output is correct
21 Correct 18 ms 13344 KB Output is correct
22 Correct 193 ms 14768 KB Output is correct
23 Correct 219 ms 14872 KB Output is correct
24 Correct 299 ms 14872 KB Output is correct
25 Correct 223 ms 14872 KB Output is correct
26 Correct 215 ms 14872 KB Output is correct
27 Correct 210 ms 14920 KB Output is correct
28 Correct 187 ms 14920 KB Output is correct
29 Correct 214 ms 14920 KB Output is correct
30 Correct 199 ms 14920 KB Output is correct
31 Correct 189 ms 14980 KB Output is correct
32 Correct 577 ms 31320 KB Output is correct
33 Correct 470 ms 31320 KB Output is correct
34 Correct 525 ms 31492 KB Output is correct
35 Correct 501 ms 31492 KB Output is correct
36 Correct 453 ms 31512 KB Output is correct
37 Correct 495 ms 35540 KB Output is correct
38 Correct 453 ms 40288 KB Output is correct
39 Correct 570 ms 44852 KB Output is correct
40 Correct 456 ms 49360 KB Output is correct
41 Correct 459 ms 52176 KB Output is correct
42 Correct 520 ms 52176 KB Output is correct
43 Correct 470 ms 52176 KB Output is correct
44 Correct 450 ms 52176 KB Output is correct
45 Correct 423 ms 52176 KB Output is correct
46 Correct 414 ms 52176 KB Output is correct
47 Correct 524 ms 55028 KB Output is correct
48 Correct 320 ms 57868 KB Output is correct
49 Correct 273 ms 62136 KB Output is correct
50 Runtime error 312 ms 65840 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.
51 Halted 0 ms 0 KB -