fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define mp make_pair
  4. using namespace std;
  5. typedef pair<int, long long> PII;
  6. main(){
  7.     freopen("runaway.in", "r", stdin);
  8.     freopen("runaway.out", "w", stdout);
  9.     int N; cin >> N; long long L; cin >> L;
  10.     PII prevnode[N+1];
  11.     PII jump[N+1][20];
  12.     vector<int> graph[N+1];
  13.     prevnode[0] = mp(0, 0);
  14.     map<int, int> marked;
  15.     int dp[N+1];
  16.     for (int i = 2; i <= N; i++){
  17.         int p; long long l; scanf("%d %I64d", &p, &l); graph[p].push_back(i);
  18.         prevnode[i] = mp(p, l);
  19.     }
  20.     jump[0][0] = mp(0, 0);
  21.     for (int i = 1; i <= N; i++){
  22.         jump[i][0] = prevnode[i];
  23.     }
  24.     for (int i = 1; i <= N; i++){
  25.         for (int j = 1; j < 20; j++){
  26.             jump[i][j] = mp(jump[(jump[i][j-1].first)][j-1].first, jump[i][j-1].second + jump[(jump[i][j-1].first)][j-1].second);
  27.         }
  28.     }
  29.  
  30.     for (int i = 1; i <= N; i++){
  31.         long long temp = L;
  32.         int node = i;
  33.         for (int j = 19; j >= 0; j--){
  34.             if (jump[node][j].second <= temp && (jump[node][j].first)){
  35.                 temp -= jump[node][j].second;
  36.                 node = jump[node][j].first;
  37.             }
  38.         }
  39.         marked[prevnode[node].first]++;
  40.     }
  41.     memset(dp, 0, sizeof(dp));
  42.     for (int i = N; i >= 1; i--){
  43.         for (int k: graph[i]){
  44.             dp[i] += dp[k];
  45.         }
  46.         dp[i]++;
  47.         dp[i] -= marked[i];
  48.     }
  49.     for (int i = 1; i <= N; i++){
  50.         printf("%I64d\n", dp[i]);
  51.     }
  52.     return 0;
  53.  
  54. }
  55.  
Runtime error #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cV0eKj
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!