fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node{
  5.     vector<int> child;
  6.     int req=-1;
  7. };
  8. int total=0;
  9. node nodes[20000];
  10. void build(int root){
  11.     if(!nodes[root].child.empty()){
  12.         for(int i=0;i<nodes[root].child.size();i++){
  13.             build( nodes[root].child[i] );
  14.             nodes[root].req+= nodes[  nodes[root].child[i] ].req;
  15.  
  16.         }
  17.     }
  18.     total+=  abs( nodes[root].req );
  19. }
  20.  
  21. void apple(int root){
  22.     if( !nodes[root].child.empty() ){
  23.         for(int i=0;i<nodes[root].child.size();i++){
  24.            // total+=abs( nodes[ nodes[root].child[i] ].req);
  25.             //cout<<"root: "<<root<<", "<<total<<"\n";
  26.             apple( nodes[root].child[i]);
  27.  
  28.         }
  29.     }
  30. }
  31. int main(){
  32.     int n,tmp,m;
  33.     cin>>n;
  34.  
  35.     int roots[20000];
  36.     for(int i=0;i<=n;i++) roots[i]=-1;
  37.     for(int i=1;i<=n;i++){
  38.         cin>>tmp;
  39.         cin>>tmp;
  40.         nodes[i].req+=tmp;
  41.         cin>>m;
  42.         for(int j=0;j<m;j++){
  43.             cin>>tmp;
  44.             nodes[i].child.push_back(tmp);
  45.             roots[tmp]=i;
  46.         }
  47.     }
  48.     int root;
  49.     for(int i=1;i<=n;i++){
  50.         if(roots[i]==-1) root = i;
  51.     }
  52.     /*
  53.     for(int i=1;i<=n;i++){
  54.     	cout<<roots[i]<<" ";
  55.     }
  56.     cout<<"\n";
  57.     */
  58.     //recursion to build tree
  59.     for(int i=1;i<=n;i++){
  60.     	//cout<<i<<": "<<nodes[i].req<<"\n";
  61.     }
  62.     build( root );
  63.     //cout<<"after: \n";
  64.     for(int i=1;i<=n;i++){
  65.     //	cout<<i<<": "<<nodes[i].req<<"\n";
  66.     }
  67.     apple(root);
  68.     cout<<total<<"\n";
  69. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
9
1 0 3 2 3 4
2 9 0
3 0 2 5 6
4 0 3 7 8 9
5 0 0
6 0 0
7 0 0
8 0 0
9 0 0
stdout
copy 
20
https://ideone.com/gWYrt0
language:
C++ (gcc 8.3)
created:
11 days 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!