oj.uz

Submission #58768

# Submission time Handle Problem Language Result Execution time Memory
58768 2018-07-19T09:40:34 Z andy627 None (KOI16_tree) C++17
36 / 100
 602 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[ele<<1];

vector<int> edge[222222];

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

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 11 ms 5624 KB Output is correct
2 Correct 11 ms 5864 KB Output is correct
3 Correct 9 ms 5864 KB Output is correct
4 Correct 10 ms 5940 KB Output is correct
5 Correct 11 ms 6112 KB Output is correct
6 Correct 10 ms 6112 KB Output is correct
7 Correct 10 ms 6112 KB Output is correct
8 Correct 11 ms 6216 KB Output is correct
9 Correct 11 ms 6232 KB Output is correct
10 Correct 11 ms 6248 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5624 KB Output is correct
2 Correct 11 ms 5864 KB Output is correct
3 Correct 9 ms 5864 KB Output is correct
4 Correct 10 ms 5940 KB Output is correct
5 Correct 11 ms 6112 KB Output is correct
6 Correct 10 ms 6112 KB Output is correct
7 Correct 10 ms 6112 KB Output is correct
8 Correct 11 ms 6216 KB Output is correct
9 Correct 11 ms 6232 KB Output is correct
10 Correct 11 ms 6248 KB Output is correct
11 Correct 10 ms 6392 KB Output is correct
12 Correct 8 ms 6392 KB Output is correct
13 Correct 9 ms 6408 KB Output is correct
14 Correct 10 ms 6424 KB Output is correct
15 Correct 10 ms 6440 KB Output is correct
16 Correct 11 ms 6456 KB Output is correct
17 Correct 10 ms 6532 KB Output is correct
18 Correct 8 ms 6532 KB Output is correct
19 Correct 11 ms 6532 KB Output is correct
20 Correct 10 ms 6532 KB Output is correct
21 Correct 8 ms 6556 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5624 KB Output is correct
2 Correct 11 ms 5864 KB Output is correct
3 Correct 9 ms 5864 KB Output is correct
4 Correct 10 ms 5940 KB Output is correct
5 Correct 11 ms 6112 KB Output is correct
6 Correct 10 ms 6112 KB Output is correct
7 Correct 10 ms 6112 KB Output is correct
8 Correct 11 ms 6216 KB Output is correct
9 Correct 11 ms 6232 KB Output is correct
10 Correct 11 ms 6248 KB Output is correct
11 Correct 10 ms 6392 KB Output is correct
12 Correct 8 ms 6392 KB Output is correct
13 Correct 9 ms 6408 KB Output is correct
14 Correct 10 ms 6424 KB Output is correct
15 Correct 10 ms 6440 KB Output is correct
16 Correct 11 ms 6456 KB Output is correct
17 Correct 10 ms 6532 KB Output is correct
18 Correct 8 ms 6532 KB Output is correct
19 Correct 11 ms 6532 KB Output is correct
20 Correct 10 ms 6532 KB Output is correct
21 Correct 8 ms 6556 KB Output is correct
22 Correct 204 ms 9520 KB Output is correct
23 Correct 217 ms 11936 KB Output is correct
24 Correct 266 ms 13936 KB Output is correct
25 Correct 232 ms 16272 KB Output is correct
26 Correct 227 ms 18484 KB Output is correct
27 Correct 179 ms 20752 KB Output is correct
28 Correct 247 ms 22936 KB Output is correct
29 Correct 200 ms 25220 KB Output is correct
30 Correct 166 ms 27636 KB Output is correct
31 Correct 203 ms 29708 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5624 KB Output is correct
2 Correct 11 ms 5864 KB Output is correct
3 Correct 9 ms 5864 KB Output is correct
4 Correct 10 ms 5940 KB Output is correct
5 Correct 11 ms 6112 KB Output is correct
6 Correct 10 ms 6112 KB Output is correct
7 Correct 10 ms 6112 KB Output is correct
8 Correct 11 ms 6216 KB Output is correct
9 Correct 11 ms 6232 KB Output is correct
10 Correct 11 ms 6248 KB Output is correct
11 Correct 482 ms 50264 KB Output is correct
12 Correct 532 ms 54636 KB Output is correct
13 Correct 566 ms 58796 KB Output is correct
14 Correct 602 ms 63032 KB Output is correct
15 Runtime error 575 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.
16 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5624 KB Output is correct
2 Correct 11 ms 5864 KB Output is correct
3 Correct 9 ms 5864 KB Output is correct
4 Correct 10 ms 5940 KB Output is correct
5 Correct 11 ms 6112 KB Output is correct
6 Correct 10 ms 6112 KB Output is correct
7 Correct 10 ms 6112 KB Output is correct
8 Correct 11 ms 6216 KB Output is correct
9 Correct 11 ms 6232 KB Output is correct
10 Correct 11 ms 6248 KB Output is correct
11 Correct 10 ms 6392 KB Output is correct
12 Correct 8 ms 6392 KB Output is correct
13 Correct 9 ms 6408 KB Output is correct
14 Correct 10 ms 6424 KB Output is correct
15 Correct 10 ms 6440 KB Output is correct
16 Correct 11 ms 6456 KB Output is correct
17 Correct 10 ms 6532 KB Output is correct
18 Correct 8 ms 6532 KB Output is correct
19 Correct 11 ms 6532 KB Output is correct
20 Correct 10 ms 6532 KB Output is correct
21 Correct 8 ms 6556 KB Output is correct
22 Correct 204 ms 9520 KB Output is correct
23 Correct 217 ms 11936 KB Output is correct
24 Correct 266 ms 13936 KB Output is correct
25 Correct 232 ms 16272 KB Output is correct
26 Correct 227 ms 18484 KB Output is correct
27 Correct 179 ms 20752 KB Output is correct
28 Correct 247 ms 22936 KB Output is correct
29 Correct 200 ms 25220 KB Output is correct
30 Correct 166 ms 27636 KB Output is correct
31 Correct 203 ms 29708 KB Output is correct
32 Correct 482 ms 50264 KB Output is correct
33 Correct 532 ms 54636 KB Output is correct
34 Correct 566 ms 58796 KB Output is correct
35 Correct 602 ms 63032 KB Output is correct
36 Runtime error 575 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.
37 Halted 0 ms 0 KB -