Submission #58769

#	Time	Username	Problem	Language	Result	Execution time	Memory
58769		andy627	트리 (KOI16_tree)	C++17	55 / 100	577 ms	65840 KiB

tree

#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 (stderr)

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 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 19 / 19
• Subtask 5: 0 / 45