fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct LCT {
  5. struct Node {
  6. int ch[2], fa;
  7. int val, mx; // trọng số cạnh nối tới cha
  8. int id_mx;   // id của cạnh có trọng số lớn nhất trên đường
  9. bool rev;
  10. };
  11. vector<Node> t;
  12.  
  13.  
  14. LCT(int n = 0) { t.assign(n + 1, {}); }
  15.  
  16. bool isRoot(int x) {
  17.     int f = t[x].fa;
  18.     return f == 0 || (t[f].ch[0] != x && t[f].ch[1] != x);
  19. }
  20.  
  21. void pushUp(int x) {
  22.     t[x].mx = t[x].val;
  23.     t[x].id_mx = x;
  24.     for (int d = 0; d < 2; ++d) {
  25.         int y = t[x].ch[d];
  26.         if (y && t[y].mx > t[x].mx) {
  27.             t[x].mx = t[y].mx;
  28.             t[x].id_mx = t[y].id_mx;
  29.         }
  30.     }
  31. }
  32.  
  33. void pushRev(int x) {
  34.     swap(t[x].ch[0], t[x].ch[1]);
  35.     t[x].rev ^= 1;
  36. }
  37.  
  38. void pushDown(int x) {
  39.     if (t[x].rev) {
  40.         if (t[x].ch[0]) pushRev(t[x].ch[0]);
  41.         if (t[x].ch[1]) pushRev(t[x].ch[1]);
  42.         t[x].rev = 0;
  43.     }
  44. }
  45.  
  46. void rotate(int x) {
  47.     int y = t[x].fa, z = t[y].fa;
  48.     int k = (t[y].ch[1] == x);
  49.     if (!isRoot(y)) t[z].ch[t[z].ch[1] == y] = x;
  50.     t[x].fa = z;
  51.     t[y].ch[k] = t[x].ch[k ^ 1];
  52.     if (t[x].ch[k ^ 1]) t[t[x].ch[k ^ 1]].fa = y;
  53.     t[x].ch[k ^ 1] = y;
  54.     t[y].fa = x;
  55.     pushUp(y);
  56.     pushUp(x);
  57. }
  58.  
  59. void pushAll(int x) {
  60.     if (!isRoot(x)) pushAll(t[x].fa);
  61.     pushDown(x);
  62. }
  63.  
  64. void splay(int x) {
  65.     pushAll(x);
  66.     while (!isRoot(x)) {
  67.         int y = t[x].fa, z = t[y].fa;
  68.         if (!isRoot(y))
  69.             (t[z].ch[0] == y) ^ (t[y].ch[0] == x) ? rotate(x) : rotate(y);
  70.         rotate(x);
  71.     }
  72.     pushUp(x);
  73. }
  74.  
  75. void access(int x) {
  76.     int last = 0;
  77.     for (int y = x; y; y = t[y].fa) {
  78.         splay(y);
  79.         t[y].ch[1] = last;
  80.         pushUp(y);
  81.         last = y;
  82.     }
  83.     splay(x);
  84. }
  85.  
  86. void makeRoot(int x) {
  87.     access(x);
  88.     pushRev(x);
  89. }
  90.  
  91. int findRoot(int x) {
  92.     access(x);
  93.     while (t[x].ch[0]) {
  94.         pushDown(x);
  95.         x = t[x].ch[0];
  96.     }
  97.     splay(x);
  98.     return x;
  99. }
  100.  
  101. void link(int x, int y) {
  102.     makeRoot(x);
  103.     if (findRoot(y) != x) t[x].fa = y;
  104. }
  105.  
  106. void cut(int x, int y) {
  107.     makeRoot(x);
  108.     access(y);
  109.     if (t[y].ch[0] == x) {
  110.         t[y].ch[0] = t[x].fa = 0;
  111.         pushUp(y);
  112.     }
  113. }
  114.  
  115. // Cập nhật trọng số cạnh (nút đại diện cho cạnh)
  116. void setVal(int x, int v) {
  117.     t[x].val = v;
  118.     pushUp(x);
  119. }
  120.  
  121. // Truy vấn cạnh lớn nhất trên đường u-v
  122. pair<int,int> queryMax(int u, int v) {
  123.     makeRoot(u);
  124.     access(v);
  125.     return {t[v].mx, t[v].id_mx};
  126. }
  127.  
  128.  
  129. };
  130.  
  131. struct Edge {
  132. int u, v, w;
  133. };
  134.  
  135. int main() {
  136. ios::sync_with_stdio(false);
  137. cin.tie(nullptr);
  138.  
  139.  
  140. int n, m;
  141. cin >> n >> m;
  142. int total = n + m; // node 1..n là đỉnh, n+1..n+m là cạnh
  143.  
  144. LCT lct(total);
  145. vector<Edge> edges(m + 1);
  146.  
  147. for (int i = 1; i <= m; i++) {
  148.     int u, v, w, s, t_;
  149.     cin >> u >> v >> w >> s >> t_;
  150.     edges[i] = {u, v, w};
  151.  
  152.     int e = n + i;
  153.     lct.setVal(e, w);
  154.  
  155.     int ru = lct.findRoot(u), rv = lct.findRoot(v);
  156.     if (ru != rv) {
  157.         lct.link(u, e);
  158.         lct.link(e, v);
  159.     } else {
  160.         auto [mx, id] = lct.queryMax(u, v);
  161.         if (mx > w) {
  162.             int eid = id - n;
  163.             lct.cut(edges[eid].u, id);
  164.             lct.cut(edges[eid].v, id);
  165.             lct.link(u, e);
  166.             lct.link(e, v);
  167.             edges[eid] = edges[i]; // cập nhật cạnh bị thay
  168.         }
  169.     }
  170.  
  171.     if (lct.findRoot(s) == lct.findRoot(t_)) {
  172.         cout << lct.queryMax(s, t_).first << "\n";
  173.     } else {
  174.         cout << -1 << "\n";
  175.     }
  176. }
  177. return 0;
  178.  
  179.  
  180. }
  181.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
6 8
1 2 4 1 4
1 4 5 2 4
2 5 7 4 5
3 5 6 4 3
4 5 1 2 5
3 6 3 4 6
5 6 2 2 6
1 5 4 2 3
stdout
copy 
-1
5
7
7
5
6
5
4
https://ideone.com/Oscfe3
language:
C++14 (gcc 8.3)
created:
1 day 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!