fork download
copy 
  1. #include <stdio.h>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 1e5 + 5, MAXL = 17;
  7.  
  8. int dp[MAXN][MAXL], W[MAXN], L[MAXN], T, N, Q, t = 1;
  9.  
  10. int query(int u, int k){
  11.   int log = 1;
  12.   for(; (1<<log)<=L[u]; log++);
  13.   log--;
  14.   for(; log>=0; --log) if(dp[u][log] != -1 && W[dp[u][log]] >= k) u = dp[u][log];
  15.   return u;
  16. }
  17.  
  18. int main(){
  19.   scanf("%d", &T);
  20.   while(T--){
  21.     int u, k;
  22.     scanf("%d %d", &N, &Q);
  23.     for(int i=0; i<N; ++i)
  24.       for(int j=1; (1<<j)<N; ++j) dp[i][j] = -1;
  25.     for(int i=1; i<N; ++i){
  26.       scanf("%d %d", &u, &W[i]);
  27.       dp[i][0] = u, L[i] = L[u] + 1;
  28.     }
  29.     W[0] = 1;
  30.     for(int j=1; (1<<j)<N; ++j)
  31.       for(int i=0; i<N; ++i)
  32.         if(dp[i][j - 1] != -1) dp[i][j] = dp[dp[i][j - 1]][j - 1];
  33.     printf("Case %d:\n", t++);
  34.     while(Q--){
  35.       scanf("%d %d", &u, &k);
  36.       printf("%d\n", query(u, k));
  37.     }
  38.   }
  39.   return 0;
  40. }
Success #stdin #stdout 0s 10888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WPiR2U
language:
C++14 (gcc 8.3)
created:
7 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!