Submission #36235

#	Time	Username	Problem	Language	Result	Execution time	Memory
36235		moonrabbit2	트리 (KOI16_tree)	C++11	22 / 100	2000 ms	23564 KiB

tree

#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int>g[N];
int p[N],clr[N],c_clr=1;
int n,q;
bool visit[N];
int dfs_sz(int curr)
{
    if(curr==0||curr==-1)
        return 0;
    visit[curr]=true;
    int res=1;
    if(g[curr].size()==0){
        return 1;
    }
    for(int i=0;i<g[curr].size();i++)
        if(p[g[curr][i]]==curr)
            res+=dfs_sz(g[curr][i]);
    if(p[curr]!=-1&&!visit[p[curr]])
        res+=dfs_sz(p[curr]);
    visit[curr]=false;
    return res;
}
void dfs_clr(int curr)
{
    if(curr==0||curr==-1)
        return;
    visit[curr]=true;
    clr[curr]=c_clr;
    for(int i=0;i<g[curr].size();i++)
        if(p[g[curr][i]]==curr)
            dfs_clr(g[curr][i]);
    if(p[curr]!=-1&&!visit[p[curr]])
        dfs_clr(p[curr]);
    visit[curr]=false;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        int parent;
        cin>>parent;
        p[i]=parent;
        g[parent].push_back(i);
    }
    while(q--){
        int b,c,d;
        cin>>b>>c>>d;
        if(!d){
            if(clr[b]==clr[c])
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
            continue;
        }
        if(clr[b]==clr[c]){
            cout<<"YES"<<endl;
            int tmp=p[b];
            if(p[b]==-1)
                continue;
            p[b]=-1;
            int szb=dfs_sz(b);
            int szp=dfs_sz(tmp);
            if(szb<szp){
                dfs_clr(b);
                c_clr++;
            }
            else{
                dfs_clr(tmp);
                c_clr++;
            }
        }
        else{
            cout<<"NO"<<endl;
            int tmp=p[c];
            if(p[c]==-1)
                continue;
            p[c]=-1;
            int szc=dfs_sz(c),szp=dfs_sz(tmp);
            if(szc<szp){
                dfs_clr(c);
                c_clr++;
            }
            else{
                dfs_clr(tmp);
                c_clr++;
            }
        }
    }
    return 0;
}

Compilation message (stderr)

tree.cpp: In function 'int dfs_sz(int)':
tree.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[curr].size();i++)
                  ^
tree.cpp: In function 'void dfs_clr(int)':
tree.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[curr].size();i++)
                  ^

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