fork download
copy 
  1. #pragma comment(linker, "/stack:200000000")
  2. #pragma GCC optimize("Ofast")
  3. // #pragma GCC optimize ("unroll-loops")
  4. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
  5. // #pragma GCC target("avx,avx2,fma")
  6. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") // yandex
  7.  
  8. #include "bits/stdc++.h"
  9. using namespace std;
  10. #ifndef LOCAL
  11. #define endl '\n'
  12. #endif
  13.  
  14. #define fr(i, a, b) for(int i = a; i <= b; i++)
  15. #define rf(i, a, b) for(int i = a; i >= b; i--)
  16. #define pf push_front
  17. #define pb push_back
  18. #define eb emplace_back
  19. #define fi first
  20. #define se second
  21. #define all(x) x.begin(), x.end()
  22. #define rall(x) x.rbegin(), x.rend()
  23. #define sz(x) (int)x.size()
  24. #define lb lower_bound
  25. #define ub upper_bound
  26.  
  27. typedef long long ll;
  28. typedef long double f80;
  29. typedef pair<int,int> pii;
  30. typedef pair<ll,ll> pll;
  31.  
  32. int pct(int x) { return __builtin_popcount(x); }
  33. int pct(ll x) { return __builtin_popcountll(x); }
  34. int bt(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
  35. int bt(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
  36. int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
  37. ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
  38. int nxt_C(int x) { int c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
  39. ll nxt_C(ll x) { ll c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
  40.  
  41. vector<int> get_bits(int mask) {
  42. 	vector<int> bb;
  43. 	while(mask) { int b = bt(mask); bb.pb(b); mask ^= (1 << b); }
  44. 	reverse(all(bb));
  45. 	return bb;
  46. }
  47.  
  48. int get_mask(vector<int> v) {
  49. 	int mask = 0;
  50. 	for(int x : v) { mask ^= (1 << x); }
  51. 	return mask;
  52. }
  53.  
  54. template<typename T>
  55. void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }
  56.  
  57. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  58.  
  59. ll rand(ll l, ll r){
  60. 	uniform_int_distribution<ll> uid(l, r);
  61. 	return uid(rng);
  62. }
  63.  
  64. void sc() {}
  65.  
  66. template <typename Head, typename... Tail>
  67. void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }
  68.  
  69. #ifdef LOCAL
  70. #define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  71. #else
  72. #define debug(...) 42
  73. #endif
  74.  
  75. // #ifndef LOCAL
  76. // string to_string(__int128 x) {
  77. // 	string s = "";
  78. // 	bool neg = 0;
  79. // 	if(x < 0) { s += "-"; neg = 1; x = -x; }
  80. // 	if(!x) s += '0';
  81. // 	while(x) {
  82. // 		int rem = x % 10;
  83. // 		s += to_string(rem);
  84. // 		x /= 10;
  85. // 	}
  86. // 	reverse(s.begin() + neg, s.end());
  87. // 	return s;
  88. // }
  89. // #endif
  90.  
  91. const int mod = 1e9 + 7; // 998244353;
  92.  
  93. int pwr(int a,ll b) {
  94. 	int ans = 1;
  95. 	while(b) {
  96. 		if(b & 1) ans = (ans * 1LL * a) % mod;
  97. 		a = (a * 1LL * a) % mod;
  98. 		b >>= 1;
  99. 	}
  100. 	return ans;
  101. }
  102.  
  103. /*
  104. 	Lookout for overflows!!
  105. 	Check array sizes!!
  106. 	Clear before test cases!!
  107. 	Use the correct modulo!!
  108. 	Check for corner cases!!
  109. 	Are you forgetting something?!
  110. 	Read problem statement carefully!!!
  111. */
  112.  
  113. const int N = 1e6 + 5;
  114. const int LOGN = 20;
  115. vector<int> g[N];
  116. bool centroid[N];
  117.  
  118. int depth[N], par[N], sz[N];
  119. int dist_par[N][LOGN], dsz[N];
  120. vector<pii> dis_child[N];
  121. bool tmp[N];
  122. pii qq[N];
  123.  
  124. void dfs2(int u,int p){
  125.     tmp[u] = 0;
  126.     sz[u] = 1;
  127.     for(int v : g[u])
  128.         if(v != p && !centroid[v]){
  129.             dfs2(v, u);
  130.             sz[u] += sz[v];
  131.         }
  132. }
  133.  
  134. int get(int u,int p,int S){
  135.     for(int v : g[u])
  136.         if(v != p && !centroid[v] && sz[v] > S / 2)
  137.             return get(v, u, S);
  138.     return u;
  139. }
  140.  
  141. int solve(int u){
  142.     dfs2(u, 0);
  143.     int c = get(u, 0, sz[u]);
  144.     centroid[c] = 1;
  145.     int l = 0, r = 0;
  146.     qq[r++] = {0, c};
  147.     tmp[c] = 1;
  148.     pii x;
  149.     while(l < r) {
  150.         x = qq[l++];
  151.         dis_child[c].eb(x);
  152.         dist_par[x.se][dsz[x.se]++] = x.fi;
  153.         int u = x.se;
  154.         for(int v : g[u]) {
  155.             if(!tmp[v] && !centroid[v]) {
  156.                 tmp[v] = 1;
  157.                 qq[r++] = {x.fi + 1, v};
  158.             }
  159.         }
  160.     }
  161.     for(int v : g[c])
  162.         if(!centroid[v]) {
  163.             par[solve(v)] = c;
  164.         }
  165.     return c;
  166. }
  167. void dfs1(int u,int p) {
  168.     depth[u] = depth[p] + 1;
  169.     for(int v : g[u])
  170.         if(v != p)
  171.             dfs1(v, u);
  172. }
  173.  
  174. ll c[N];
  175. bool vis[N];
  176. set<pair<ll,int>> q;
  177.  
  178. void solve() {
  179.     int n, m, a, b;
  180.     sc(n, m, a, b);
  181.     q.clear();
  182.     fr(i, 1, n) {
  183.         dis_child[i].clear();
  184.         dsz[i] = 0;
  185.         g[i].clear();
  186.         centroid[i] = 0;
  187.         vis[i] = 0;
  188.         par[i] = 0;
  189.     }
  190.     fr(i, 1, n) {
  191.         int p;
  192.         sc(p, c[i]);
  193.         // p = i - 1, c[i] = 1;
  194.         if(!c[i]) c[i] = 1e18;
  195.         if(p) {
  196.             g[p].eb(i);
  197.             g[i].eb(p);
  198.         }
  199.     }
  200.     c[a] = c[b] = 0;
  201.     solve(1);
  202.     fr(i, 1, n) {
  203.         reverse(dist_par[i], dist_par[i] + dsz[i]);
  204.         reverse(all(dis_child[i]));
  205.     }
  206.     q.emplace(0, a);
  207.     vis[a] = 1;
  208.     ll ans = -1;
  209.     while(!q.empty()) {
  210.         auto x = *q.begin();
  211.         q.erase(q.begin());
  212.         int u = x.se;
  213.         ll val = x.fi;
  214.         if(val >= 1e18) break;
  215.         if(u == b) { ans = val; break; }
  216.         int p = u, k = 0;
  217.         while(p) {
  218.             int d = dist_par[u][k];
  219.             while(!dis_child[p].empty() && dis_child[p].back().fi <= m - d) {
  220.                 int v = dis_child[p].back().se;
  221.                 dis_child[p].pop_back();
  222.                 if(!vis[v]) {
  223.                     vis[v] = 1;
  224.                     q.emplace(c[v] + val, v);
  225.                 }
  226.             }
  227.             p = par[p], k++;
  228.         }
  229.     }
  230.     cout << ans << endl;
  231. }
  232.  
  233. int main() {
  234. 	ios :: sync_with_stdio(0);
  235. 	cin.tie(0);
  236. 	cout.tie(0);
  237. 	int t = 1;
  238. 	cin >> t;
  239. 	for(int tt = 1; tt <= t; tt++) {
  240.         cout << "Case #" << tt << ": ";
  241. 		solve();
  242. 	}
  243. 	return 0;
  244. }
Runtime error #stdin #stdout 0.02s 50220KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QXAkfJ
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!