fork download
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<queue>
  4. #include<cstring>
  5. using namespace std;
  6. typedef struct node {
  7. long start;
  8. long death;
  9. } ii;
  10. long dp[70001];
  11. ii nodes[70001];
  12. int N;
  13. int bfs(long start, vector < vector < long > >&Graph)
  14. {
  15. long i;
  16. long deathMain = nodes[start].death;
  17. dp[start] = 0;
  18. queue < long >Q;
  19. Q.push(start);
  20. while (!Q.empty()) {
  21. int current = Q.front();
  22. Q.pop();
  23. for (i = 0; i < Graph[current].size(); i++) {
  24. if (nodes[Graph[current][i]].start <= deathMain) {
  25. Q.push(Graph[current][i]);
  26. dp[Graph[current][i]] = dp[current] + 1;
  27. }
  28. }
  29. }
  30. }
  31.  
  32. int main()
  33. {
  34. int test;
  35. cin >> test;
  36. long i;
  37. while (test--) {
  38. scanf("%ld", &N);
  39. vector < vector < long > >Graph(N + 1);
  40. long i, parent, death, start;
  41. for (i = 1; i <= N; i++) {
  42. scanf("%ld %ld %ld", &parent, &start, &death);
  43. nodes[i].start = start;
  44. nodes[i].death = death;
  45. parent++;
  46. Graph[parent].push_back(i);
  47. }
  48. long j;
  49. for (i = 1; i <= N; i++) {
  50. memset(dp, 0, sizeof(dp));
  51. bfs(i, Graph);
  52. long ans = 0;
  53. for (j = 1; j <= N; j++)
  54. ans = max(ans, dp[j]);
  55. printf("%ld ", ans);
  56.  
  57.  
  58. }
  59.  
  60. printf("\n");
  61. }
  62. }
  63.  
Success #stdin #stdout 0.01s 3684KB
stdin
2

5

-1 0 10

0 1 5

0 2 8

0 2 5

3 10 12

9

-1 0 10

0 1 1

0 2 2

1 2 3

1 3 4

2 2 3

2 2 4

6 10 11

6 20 30

 
stdout
2 0 0 0 0 
3 0 1 0 0 0 0 0 0