fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define maxn 200005
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int INFTY = 1e9 + 1;
  12.  
  13. int n, m;
  14. int lab[maxn], sz[maxn], parent[maxn], weight[maxn];
  15. int visited;
  16.  
  17. inline void Minimize(int& Target, int Value)
  18. {
  19.     if (Value < Target) Target = Value;
  20. }
  21.  
  22. void Init()
  23. {
  24.     for (int u = 1; u <= n; ++u)
  25.     {
  26.         sz[u] = 1;
  27.         parent[u] = 0;
  28.     }
  29.     fill(lab + 1, lab + n + 1, 0);
  30.     visited = 0;
  31. }
  32.  
  33. void AddChild(int p, int c)
  34. {
  35.     parent[c] = p;
  36.     if (p != 0)
  37.         sz[p] += sz[c];
  38. }
  39.  
  40. void RemoveChild(int p, int c)
  41. {
  42.     parent[c] = 0;
  43.     sz[p] -= sz[c];
  44. }
  45.  
  46. void UpTree(int x)
  47. {
  48.     int y = parent[x];
  49.     int z = parent[y];
  50.     if (z != 0)
  51.         RemoveChild(z, y);
  52.     RemoveChild(y, x);
  53.     if (z != 0 && weight[x] < weight[y])
  54.     {
  55.         AddChild(z, x);
  56.         AddChild(z, y);
  57.     }
  58.     else
  59.     {
  60.         AddChild(x, y);
  61.         AddChild(z, x);
  62.         swap(weight[x], weight[y]);
  63.     }
  64. }
  65.  
  66. void Calibrate(int x)
  67. {
  68.     while (parent[x] != 0)
  69.         if ((ll)sz[x] * 3 > (ll)sz[parent[x]] * 2)
  70.             UpTree(x);
  71.         else
  72.             x = parent[x];
  73. }
  74.  
  75. int PathMin(int s, int t)
  76. {
  77.     Calibrate(s);
  78.     Calibrate(t);
  79.     int a = 0;
  80.     ++visited;
  81.     for (int i = s; i != 0; i = parent[i]) lab[i] = visited;
  82.     for (int i = t; i != 0; i = parent[i])
  83.         if (lab[i] == visited)
  84.         {
  85.             a = i; break;
  86.         }
  87.     if (a == 0) return -1;
  88.     int res = INFTY;
  89.     for (int i = s; i != a; i = parent[i])
  90.         Minimize(res, weight[i]);
  91.     for (int i = t; i != a; i = parent[i])
  92.         Minimize(res, weight[i]);
  93.     return res;
  94. }
  95.  
  96. void AddEdge(int u, int v, int b)
  97. {
  98.     int temp = PathMin(u, v);
  99.     if (temp >= b) return;
  100.     while (parent[v] != 0) UpTree(v);
  101.     while (parent[u] != 0) UpTree(u);
  102.     weight[v] = b;
  103.     if (parent[v] != u)
  104.         AddChild(u, v);
  105. }
  106.  
  107. signed main()
  108. {
  109.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  110.     cin >> n >> m;
  111.     if(n<=200){
  112.         Init();
  113.         while (m-- > 0)
  114.         {
  115.             int u, v, w, s, t;
  116.             cin >> u >> v >> w >> s >> t;
  117.             AddEdge(u, v, INFTY - w);
  118.             int r = PathMin(s, t);
  119.             if (r == -1) cout << -1 << '\n';
  120.             else cout << INFTY - r << '\n';
  121.         }
  122.     }
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0Gt0Xe
language:
C++14 (gcc 8.3)
created:
9 days 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!