oj.uz

Submission #36234

# Submission time Handle Problem Language Result Execution time Memory
36234 2017-12-06T12:07:06 Z moonrabbit2 None (KOI16_tree) C++11
0 / 100
 23 ms 8620 KB 
#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;
    clr[curr]=c_clr;
    for(int i=0;i<g[curr].size();i++)
        if(p[g[curr][i]]==curr)
            dfs_clr(g[curr][i]);
    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

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:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<g[curr].size();i++)
                  ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 8620 KB Output isn't correct
2 Halted 0 ms 0 KB -