fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. vector <int> sup;
  6. vector <vector <int> > sub;
  7. vector <bool> conf;
  8. vector <bool> hap;
  9. vector <bool> used;
  10. int n, ans=0;
  11. void dfs(int v){
  12.     if(used[v]==true)
  13.         return;
  14.     for (int i=0; i<sub[v].size(); ++i){
  15.        int to=sub[v][i];
  16.        dfs(to);
  17.        if(hap[to]==false){
  18.            hap[to]=true;
  19.            if(conf[v]==false){
  20.               conf[v]=true;
  21.               hap[v]=true;
  22.               hap[to]=true;
  23.               hap[sup[v]]=true;
  24.               ++ans;
  25.            } 
  26.        }
  27.     }
  28.     used[v]=true;
  29. }
  30. int main(){
  31.     cin>>n;
  32.     sup.resize(n);
  33.     hap.resize(n);
  34.     sub.resize(n);
  35.     used.assign(n,false);
  36.     conf.assign(n,false);
  37.     hap[0]=1;
  38.     sup[0]=0;
  39.     for(int i=1; i<n; ++i){
  40.        int s,h;
  41.        cin>>s>>h;
  42.        sub[s].push_back(i);
  43.        sup[i]=s;
  44.        hap[i]=h;
  45.     }
  46.     dfs(0);
  47.     cout<<ans;
  48.     return 0;
  49. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
5
0 0
1 0
2 0
2 0
stdout
copy 
1
https://ideone.com/VIA9MG
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!