Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <vector>
- using namespace std;
- #define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
- #define pb push_back
- typedef long long i64;
- #define SDi(x) scanf("%d",&x)
- #define SD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
- #define pf printf
- #define READ(f) freopen(f, "r", stdin)
- #define Max 10010
- vector <int> adj[Max];
- int marbles[Max], parent[Max];
- i64 total_moves;
- void solve (int node) {
- rep(i, (int) adj[node].size()) {
- int child = adj[node][i];
- parent[child] = node;
- solve (child);
- }
- if (marbles[node] < 1) {
- int need = 1 - marbles[node];
- total_moves += need;
- marbles[parent[node]] -= need;
- } else {
- int extra = marbles[node] - 1;
- total_moves += extra;
- marbles[ parent[node] ] += extra;
- }
- }
- int main(void) {
- #ifndef ONLINE_JUDGE
- READ("input.txt");
- #endif
- int n, u, v, childs, marble;
- while (SDi(n) == 1 && n) {
- total_moves = 0;
- rep(i, n) {
- SD3(u, marble, childs);
- marbles[u] = marble;
- rep(j, childs) {
- SDi(v);
- adj[u].pb(v);
- }
- }
- solve(1); // assuming 1 as root, isn't it true?
- pf("%lld\n", total_moves);
- rep(i, n + 10) adj[i].clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment