oj.uz

Submission #36235

# Submission time Handle Problem Language Result Execution time Memory
36235 2017-12-06T12:10:35 Z moonrabbit2 None (KOI16_tree) C++11
22 / 100
 2000 ms 23564 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;
    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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8620 KB Output is correct
2 Correct 16 ms 8620 KB Output is correct
3 Correct 23 ms 8620 KB Output is correct
4 Correct 6 ms 8620 KB Output is correct
5 Correct 13 ms 8620 KB Output is correct
6 Correct 26 ms 8620 KB Output is correct
7 Correct 13 ms 8620 KB Output is correct
8 Correct 9 ms 8620 KB Output is correct
9 Correct 23 ms 8620 KB Output is correct
10 Correct 13 ms 8620 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8620 KB Output is correct
2 Correct 16 ms 8620 KB Output is correct
3 Correct 23 ms 8620 KB Output is correct
4 Correct 6 ms 8620 KB Output is correct
5 Correct 13 ms 8620 KB Output is correct
6 Correct 26 ms 8620 KB Output is correct
7 Correct 13 ms 8620 KB Output is correct
8 Correct 9 ms 8620 KB Output is correct
9 Correct 23 ms 8620 KB Output is correct
10 Correct 13 ms 8620 KB Output is correct
11 Correct 6 ms 8620 KB Output is correct
12 Correct 9 ms 8620 KB Output is correct
13 Correct 19 ms 8620 KB Output is correct
14 Correct 6 ms 8620 KB Output is correct
15 Correct 6 ms 8620 KB Output is correct
16 Correct 6 ms 8620 KB Output is correct
17 Correct 6 ms 8620 KB Output is correct
18 Correct 0 ms 8620 KB Output is correct
19 Correct 26 ms 8620 KB Output is correct
20 Correct 6 ms 8620 KB Output is correct
21 Correct 16 ms 8620 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8620 KB Output is correct
2 Correct 16 ms 8620 KB Output is correct
3 Correct 23 ms 8620 KB Output is correct
4 Correct 6 ms 8620 KB Output is correct
5 Correct 13 ms 8620 KB Output is correct
6 Correct 26 ms 8620 KB Output is correct
7 Correct 13 ms 8620 KB Output is correct
8 Correct 9 ms 8620 KB Output is correct
9 Correct 23 ms 8620 KB Output is correct
10 Correct 13 ms 8620 KB Output is correct
11 Correct 6 ms 8620 KB Output is correct
12 Correct 9 ms 8620 KB Output is correct
13 Correct 19 ms 8620 KB Output is correct
14 Correct 6 ms 8620 KB Output is correct
15 Correct 6 ms 8620 KB Output is correct
16 Correct 6 ms 8620 KB Output is correct
17 Correct 6 ms 8620 KB Output is correct
18 Correct 0 ms 8620 KB Output is correct
19 Correct 26 ms 8620 KB Output is correct
20 Correct 6 ms 8620 KB Output is correct
21 Correct 16 ms 8620 KB Output is correct
22 Runtime error 219 ms 8620 KB Execution timed out (wall clock limit exceeded)
23 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8620 KB Output is correct
2 Correct 16 ms 8620 KB Output is correct
3 Correct 23 ms 8620 KB Output is correct
4 Correct 6 ms 8620 KB Output is correct
5 Correct 13 ms 8620 KB Output is correct
6 Correct 26 ms 8620 KB Output is correct
7 Correct 13 ms 8620 KB Output is correct
8 Correct 9 ms 8620 KB Output is correct
9 Correct 23 ms 8620 KB Output is correct
10 Correct 13 ms 8620 KB Output is correct
11 Execution timed out 2000 ms 23564 KB Execution timed out
12 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8620 KB Output is correct
2 Correct 16 ms 8620 KB Output is correct
3 Correct 23 ms 8620 KB Output is correct
4 Correct 6 ms 8620 KB Output is correct
5 Correct 13 ms 8620 KB Output is correct
6 Correct 26 ms 8620 KB Output is correct
7 Correct 13 ms 8620 KB Output is correct
8 Correct 9 ms 8620 KB Output is correct
9 Correct 23 ms 8620 KB Output is correct
10 Correct 13 ms 8620 KB Output is correct
11 Correct 6 ms 8620 KB Output is correct
12 Correct 9 ms 8620 KB Output is correct
13 Correct 19 ms 8620 KB Output is correct
14 Correct 6 ms 8620 KB Output is correct
15 Correct 6 ms 8620 KB Output is correct
16 Correct 6 ms 8620 KB Output is correct
17 Correct 6 ms 8620 KB Output is correct
18 Correct 0 ms 8620 KB Output is correct
19 Correct 26 ms 8620 KB Output is correct
20 Correct 6 ms 8620 KB Output is correct
21 Correct 16 ms 8620 KB Output is correct
22 Runtime error 219 ms 8620 KB Execution timed out (wall clock limit exceeded)
23 Halted 0 ms 0 KB -