fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 1e6 + 87;
  5. const ll inf = 1e18;
  6. int c[N];
  7. vector<int> g[N];
  8. bool vis[N];
  9. int pa[N];
  10. void dfs(int u)
  11. {
  12.     vis[u] = 1;
  13.     for (int v : g[u])
  14.         if (!vis[v]) {
  15.             pa[v] = u;
  16.             dfs(v);
  17.         }
  18. }
  19. void solve()
  20. {
  21.     int n, m, a, b;
  22.     cin >> n >> m >> a >> b;
  23.     for (int i = 1; i <= n; ++i)
  24.         g[i].clear();
  25.     for (int i = 1; i <= n; ++i) {
  26.         int pi;
  27.         cin >> pi >> c[i];
  28.         if (pi)
  29.             g[pi].push_back(i), g[i].push_back(pi);
  30.     }
  31.     fill_n(vis, n + 1, 0);
  32.     dfs(a);
  33.     vector<int> path;
  34.     for (int i = b; i != a; i = pa[i])
  35.         path.push_back(i);
  36.     reverse(path.begin(), path.end());
  37.     fill_n(vis, n + 1, 0);
  38.     vis[a] = 1;
  39.     for (int u : path)
  40.         vis[u] = 1;
  41.     int delta = 0;
  42.     deque<pair<int, ll>> dk = {{m, 0}};
  43.     for (int u : path) {
  44.         delta -= 1;
  45.         while (dk.size() && dk[0].first + delta < 0)
  46.             dk.pop_front();
  47.         vector<int> qu = {u}, nq, co;
  48.         for (int k = 0; qu.size(); ++k) {
  49.             co.push_back(0);
  50.             nq.clear();
  51.             for (int x : qu) {
  52.                 if (co.back() == 0)
  53.                     co.back() = c[x];
  54.                 else if (c[x])
  55.                     co.back() = min(co.back(), c[x]);
  56.                 for (int y : g[x])
  57.                     if (!vis[y]) {
  58.                         vis[y] = 1;
  59.                         nq.push_back(y);
  60.                     }
  61.             }
  62.             swap(qu, nq);
  63.         }
  64.         co.resize(min(m + 1, (int)co.size()));
  65.         vector<pair<int, ll>> v1, v2;
  66.         for (int k = 0, i = 0; k < co.size(); ++k) {
  67.             while (i < dk.size() && dk[i].first + delta < k)
  68.                 ++i;
  69.             if (i == dk.size())
  70.                 break;
  71.             if (co[k])
  72.                 v1.emplace_back(m - k - delta, co[k] + dk[i].second);
  73.         }
  74.         if (v1.empty())
  75.             continue;
  76.         while (dk.size() && dk.back().first >= v1.back().first) {
  77.             v2.push_back(dk.back());
  78.             dk.pop_back();
  79.         }
  80.         auto pb = [&] (pair<int, ll> p) {
  81.             while (dk.size() && dk.back().second >= p.second)
  82.                 dk.pop_back();
  83.             if (dk.empty() || dk.back().first < p.first)
  84.                 dk.push_back(p);
  85.         };
  86.         while (v1.size() && v2.size()) {
  87.             if (v1.back().first < v2.back().first)
  88.                 pb(v1.back()), v1.pop_back();
  89.             else
  90.                 pb(v2.back()), v2.pop_back();
  91.         }
  92.         while (v1.size())
  93.             pb(v1.back()), v1.pop_back();
  94.         while (v2.size())
  95.             pb(v2.back()), v2.pop_back();
  96.     }
  97.     ll ans = dk.size() ? dk[0].second : inf;
  98.     if (ans >= inf)
  99.         cout << "-1\n";
  100.     else
  101.         cout << ans << '\n';
  102. }
  103. int main()
  104. {
  105.     ios::sync_with_stdio(0);
  106.     cin.tie(0);
  107.     int T;
  108.     cin >> T;
  109.     for (int i = 1; i <= T; ++i) {
  110.         cout << "Case #" << i << ": ";
  111.         solve();
  112.     }
  113. }
  114.  
Success #stdin #stdout 0.01s 26884KB
comments (?)
stdin 
6
4 1 2 3
0 10
4 20
4 30
1 40
8 1 5 3
0 30
3 20
1 0
7 10
8 0
1 0
6 20
6 30
8 2 5 3
0 30
3 20
1 0
7 10
8 0
1 0
6 20
6 30
8 3 5 3
0 30
3 20
1 0
7 10
8 0
1 0
6 20
6 30
15 1 3 14
0 28
1 18
1 17
2 8
4 13
4 2
2 6
5 37
8 37
9 21
6 22
2 33
1 11
8 5
12 8
15 5 11 12
0 0
7 28
1 19
6 5
15 0
5 0
15 0
1 12
8 6
5 20
2 0
4 0
6 10
4 8
1 22
stdout 
Case #1: 40
Case #2: -1
Case #3: 60
Case #4: 20
Case #5: 104
Case #6: 17
https://ideone.com/IqiaCi
language:
C++14 (gcc 8.3)
created:
4 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!