Kaidul

10672

Oct 7th, 2013
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5. #define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
  6. #define pb push_back
  7. typedef long long i64;
  8. #define SDi(x) scanf("%d",&x)
  9. #define SD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  10. #define pf printf
  11. #define READ(f) freopen(f, "r", stdin)
  12.  
  13. #define Max 10010
  14.  
  15. vector <int> adj[Max];
  16. int marbles[Max], parent[Max];
  17. i64 total_moves;
  18.  
  19. void solve (int node) {
  20.     rep(i, (int) adj[node].size()) {
  21.         int child = adj[node][i];
  22.         parent[child] = node;
  23.         solve (child);
  24.     }
  25.     if (marbles[node] < 1) {
  26.         int need = 1 - marbles[node];
  27.         total_moves += need;
  28.         marbles[parent[node]] -= need;
  29.     } else {
  30.         int extra = marbles[node] - 1;
  31.         total_moves += extra;
  32.         marbles[ parent[node] ] += extra;
  33.     }
  34. }
  35.  
  36. int main(void) {
  37. #ifndef ONLINE_JUDGE
  38.     READ("input.txt");
  39. #endif
  40.     int n, u, v, childs, marble;
  41.     while (SDi(n) == 1 && n) {
  42.         total_moves = 0;
  43.         rep(i, n) {
  44.             SD3(u, marble, childs);
  45.             marbles[u] = marble;
  46.             rep(j, childs) {
  47.                 SDi(v);
  48.                 adj[u].pb(v);
  49.             }
  50.         }
  51.         solve(1); // assuming 1 as root, isn't it true?
  52.         pf("%lld\n", total_moves);
  53.         rep(i, n + 10) adj[i].clear();
  54.     }
  55.     return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment