Submission #38869

#	Time	Username	Problem	Language	Result	Execution time	Memory
38869		moonrabbit2	트리 (KOI16_tree)	C++14	100 / 100	456 ms	38356 KiB

tree

#include <bits/stdc++.h>
#define N 200005
#define pb push_back
using namespace std;
typedef long long ll;
int n,q,par[N];
vector<int> child[N];
int sub[N],lev[N];
vector<int> chain[N];
int where[N],place[N],c_chain;
vector<ll>tree[N];
bool linked[N];
void dfs(int curr)
{
    sub[curr]=1;
    for(auto &i : child[curr]){
        lev[i]=lev[curr]+1;
        dfs(i);
        sub[curr]+=sub[i];
    }
}
void hld(int curr)
{
    where[curr]=c_chain;
    chain[c_chain].pb(curr);
    int idx=-1;
    for(auto &i : child[curr]){
        if(idx==-1||sub[i]>sub[idx])
            idx=i;
    }
    if(idx!=-1)
        hld(idx);
    for(auto &i : child[curr]){
        if(i!=idx){
            c_chain++;
            hld(i);
        }
    }
}
ll sum(int num,int pos)
{
    pos++;
    ll res=0;
    while(pos){
        res+=tree[num][pos];
        pos&=(pos-1);
    }
    return res;
}
void add(int num,int pos,ll val)
{
    pos++;
    while(pos<tree[num].size()){
        tree[num][pos]+=val;
        pos+=(pos&-pos);
    }
}
ll query_dist(int u,int v)
{
    ll res=0;
    while(where[u]!=where[v]){
        int uu=chain[where[u]][0];
        int vv=chain[where[v]][0];
        if(lev[uu]>lev[vv]){
            if(linked[uu])
                return -1;
            res+=sum(where[u],place[u])+1;
            u=par[uu];
        }
        else{
            if(linked[vv])
                return -1;
            res+=sum(where[v],place[v])+1;
            v=par[vv];
        }
    }
    if(place[v]>=place[u])
        res+=sum(where[v],place[v])-sum(where[u],place[u]);
    else
        res+=sum(where[u],place[u])-sum(where[v],place[v]);
    return res;
}
int main()
{
     scanf("%d %d",&n,&q);
     for(int i=2;i<=n;i++){
        int x;
        scanf("%d",&x);
        par[i]=x;
        child[x].pb(i);
     }
     dfs(1);
     hld(1);
     for(int i=0;i<=c_chain;i++){
        tree[i].resize(chain[i].size()+1);
        for(int j=1;j<chain[i].size();j++){
            place[chain[i][j]]=j;
            add(i,j,1);
        }
     }
     while(q--){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        if(z==0){
            if(query_dist(x,y)>=0)
                puts("YES");
            else
                puts("NO");
        }
        else{
            if(query_dist(x,y)>=0){
                puts("YES");
                linked[x]=true;
                add(where[x],place[x],-N);
            }
            else{
                puts("NO");
                linked[y]=true;
                add(where[y],place[y],-N);
            }
        }
     }
     return 0;
}

Compilation message (stderr)

tree.cpp: In function 'void add(int, int, ll)':
tree.cpp:53:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos<tree[num].size()){
              ^
tree.cpp: In function 'int main()':
tree.cpp:96:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<chain[i].size();j++){
                      ^
tree.cpp:85:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %d",&n,&q);
                          ^
tree.cpp:88:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
tree.cpp:103:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&x,&y,&z);
                                   ^

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 14 / 14
• Subtask 4: 19 / 19
• Subtask 5: 45 / 45