fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <cstring>
  7. #include <string>
  8. #include <cmath>
  9. #include <cassert>
  10. #include <ctime>
  11. #include <algorithm>
  12. #include <sstream>
  13. #include <list>
  14. #include <queue>
  15. #include <deque>
  16. #include <stack>
  17. #include <cstdlib>
  18. #include <cstdio>
  19. #include <iterator>
  20. #include <functional>
  21. #include <unordered_set>
  22. #include <unordered_map>
  23. #include <stdio.h>
  24. #include <bitset>
  25.  
  26. using namespace std;
  27.  
  28. #define ll long long
  29. #define pb push_back
  30. #define mp make_pair
  31. #define f first
  32. #define s second
  33.  
  34. const ll maxn = 1e6 + 1, maxm = 1e5 + 1;
  35. const ll mod = 998244353, inf = 1e9;
  36.  
  37. int t, b;
  38. int n;
  39. int p[maxn], s[maxn], q[maxn];
  40. ll lv[maxn], rv[maxn], is = 0;
  41. vector<int> g[maxn];
  42. void dfs(int v, int y){
  43.     if (is)
  44.         return;
  45.     for (auto to : g[v]){
  46.         dfs(to, y);
  47.     }
  48.     vector<pair<ll, int>> sc;
  49.     for (auto to : g[v]){
  50.         sc.pb(mp(lv[to] - y, 0));
  51.         sc.pb(mp(rv[to] + y, 1));
  52.     }
  53.     sc.pb(mp(s[v], 0));
  54.     sc.pb(mp(q[v], 1));
  55.     sort(sc.begin(), sc.end());
  56.     int curr = 0;
  57.     lv[v] = 1e9 + 1;
  58.     rv[v] = -1;
  59.     for (auto it : sc){
  60.         pair<ll, int> cur = it;
  61.         if (cur.s == 0){
  62.             curr += 1;    
  63.             if (curr == (int)g[v].size() + 1){
  64.                 lv[v] = min(lv[v], cur.f);
  65.                 rv[v] = max(rv[v], cur.f);
  66.             }
  67.         }
  68.         else{
  69.             if (curr == (int)g[v].size() + 1){
  70.                 rv[v] = max(rv[v], cur.f);
  71.                 lv[v] = min(lv[v], cur.f);
  72.             }
  73.             curr -= 1;
  74.         }
  75.     }
  76.     if (lv[v] > rv[v])
  77.         is = 1;
  78. }
  79. bool check(int x){
  80.     is = 0;
  81.     dfs(1, x);
  82.     return (!is);
  83. }
  84. int main(){
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(0), cout.tie(0);
  87.     cin >> t >> b;
  88.     while (t--){
  89.         cin >> n;
  90.         for (int i = 2; i <= n; ++i){
  91.             cin >> p[i];
  92.             g[p[i]].pb(i);
  93.         }
  94.         for (int i = 1; i <= n; ++i){
  95.             cin >> s[i] >> q[i];
  96.         }
  97.         int l = 0, r = 1e9, ans = - 1;
  98.         while (l <= r){
  99.             int mid = (l + r) / 2;
  100.             if (check(mid)){
  101.                  r = mid - 1, ans = mid;
  102.             }
  103.             else{
  104.                  l = mid + 1;
  105.             }
  106.         }
  107.         cout << ans << '\n';
  108.         for (int i = 1; i <= n; ++i){
  109.             g[i].clear();
  110.         }
  111.     }
  112. }
  113.  
Success #stdin #stdout 0.01s 27296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/g0QnmM
language:
C++14 (gcc 8.3)
created:
3 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!