Advertisement
BaoJIaoPisu

Untitled

Mar 14th, 2022
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.21 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. using pii = pair<int, int>;
  10. using pll = pair<ll, ll>;
  11. using pld = pair<ld, ld>;
  12.  
  13. #define fi first
  14. #define se second
  15. #define pb push_back
  16. #define pf push_front
  17. #define mp make_pair
  18. #define ins insert
  19. #define btpc __builtin_popcount
  20. #define btclz __builtin_clz
  21.  
  22. #define sz(x) (int)(x.size());
  23. #define all(x) x.begin(), x.end()
  24. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  25.  
  26. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  27.  
  28. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  29. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  30. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  31.  
  32. template<class X, class Y>
  33.     bool minimize(X &x, const Y &y) {
  34.         if (x > y)
  35.         {
  36.             x = y;
  37.             return true;
  38.         }
  39.         return false;
  40.     }
  41. template<class X, class Y>
  42.     bool maximize(X &x, const Y &y) {
  43.         if (x < y)
  44.         {
  45.             x = y;
  46.             return true;
  47.         }
  48.         return false;
  49.     }
  50.  
  51. const int MOD = 1e9 + 7; //998244353
  52.  
  53. template<class X, class Y>
  54.     void add(X &x, const Y &y) {
  55.         x = (x + y);
  56.         if(x >= MOD) x -= MOD;
  57.     }
  58.  
  59. template<class X, class Y>
  60.     void sub(X &x, const Y &y) {
  61.         x = (x - y);
  62.         if(x < 0) x += MOD;
  63.     }
  64.  
  65. /* Author : Le Ngoc Bao Anh, 11A5, LQD High School for Gifted Student*/
  66.  
  67. const ll INF = 1e9;
  68. const int N = 1e5 + 10;
  69. const int LOG = 16;
  70.  
  71. int par[N], sz[N], dp[N], depth[N];
  72. pii f[N][LOG + 2];
  73. vector<pii> g[N];
  74. bool used[N * 10];
  75. multiset<int> curr;
  76. int ans[N * 10];
  77. vector<int> son[N], a[N], b[N];
  78. struct Edges {
  79.     int u, v, w, id;
  80.  
  81.     bool operator < (const Edges & temp) const {
  82.         return w < temp.w;
  83.     }
  84. } ed[N * 10];
  85.  
  86. int find_par(int u) {
  87.     if(par[u] < 0) return u;
  88.     par[u] = find_par(par[u]);
  89.     return par[u];
  90. }
  91.  
  92. bool merge(int u, int v) {
  93.     u = find_par(u), v = find_par(v);
  94.     if(u == v) return false;
  95.     if(par[u] > par[v]) swap(u, v);
  96.     par[u] += par[v];
  97.     par[v] = u;
  98.     return true;
  99. }
  100.  
  101. void dfs(int u) {
  102.     sz[u] = 1;
  103.     for(auto v : g[u]) {
  104.         if(v.fi != f[u][0].fi) {
  105.             f[v.fi][0] = mp(u, v.se);
  106.             depth[v.fi] = depth[u] + 1;
  107.             dfs(v.fi);
  108.             sz[u] += sz[v.fi];
  109.         }
  110.     }
  111. }
  112.  
  113. pii find_d(int u, int v) {
  114.     if(depth[u] < depth[v]) swap(u, v);
  115.  
  116.     int ans = 0;
  117.     for(int i = LOG; i >= 0; i--) {
  118.         if(depth[u] - (1 << i) >= depth[v]) {
  119.             maximize(ans, f[u][i].se);
  120.             u = f[u][i].fi;
  121.         }
  122.     }
  123.  
  124.     if(u == v) return mp(v, ans);
  125.  
  126.     for(int i = LOG; i >= 0; i--) {
  127.         if(f[u][i].fi != f[v][i].fi) {
  128.             maximize(ans, f[u][i].se);
  129.             maximize(ans, f[v][i].se);
  130.             u = f[u][i].fi; v = f[v][i].fi;
  131.         }
  132.     }
  133.  
  134.     maximize(ans, f[u][0].se);
  135.     maximize(ans, f[v][0].se);
  136.     return mp(f[u][0].fi, ans);
  137. }
  138.  
  139. void dot(int u, int p, bool isBig) {
  140.     int big = -1;
  141.     for(auto nxt : g[u]) {
  142.         int v = nxt.fi;
  143.         if(v != p) {
  144.             if(big == -1 || sz[big] < sz[v]) big = v;
  145.         }
  146.     }
  147.  
  148.     for(auto nxt : g[u]) {
  149.         int v = nxt.fi;
  150.         if(v != p && v != big) {
  151.             dot(v, u, 0);
  152.         }
  153.     }
  154.  
  155.     if(big > 0) {
  156.         dot(big, u, 1);
  157.         swap(son[big], son[u]);
  158.     }
  159.     son[u].pb(u);
  160.  
  161.     for(auto nxt : g[u]) {
  162.         int v = nxt.fi;
  163.         if(v != p && v != big) {
  164.             for(auto x : son[v]) {
  165.                 for(auto d : a[x]) curr.ins(d);
  166.                 son[u].pb(x);
  167.             }
  168.  
  169.             for(auto x : son[v]) {
  170.                 for(auto d : b[x]) {
  171.                     auto iter = curr.find(d);
  172.                     assert(iter != curr.end());
  173.                     curr.erase(iter);
  174.                 }
  175.             }
  176.         }
  177.     }
  178.  
  179.     for(auto x : a[u]) curr.ins(x);
  180.     for(auto x : b[u]) {
  181.         auto iter = curr.find(x);  
  182.         assert(iter != curr.end());
  183.         curr.erase(iter);
  184.     }
  185.  
  186.     dp[u] = (curr.empty() ? INF : (*curr.begin()));
  187.     if(!isBig) curr.clear();
  188. }
  189.  
  190. void solve() {
  191.     int n, m;
  192.     cin >> n >> m;
  193.     for(int i = 1; i <= m; i++) {
  194.         int u, v, w; cin >> u >> v >> w;
  195.         ed[i] = {u, v, w, i};
  196.     }  
  197.  
  198.     for(int i = 1; i <= n; i++) par[i] = -1;
  199.     sort(ed + 1, ed + 1 + m);
  200.     for(int i = 1; i <= m; i++) {
  201.         used[i] = merge(ed[i].u, ed[i].v);
  202.         if(used[i]) {
  203.             g[ed[i].u].pb(mp(ed[i].v, ed[i].w));
  204.             g[ed[i].v].pb(mp(ed[i].u, ed[i].w));
  205.         }
  206.     }
  207.  
  208.     depth[1] = 1; dfs(1);
  209.     for(int j = 1; j <= LOG; j++) {
  210.         for(int i = 1; i <= n; i++) {
  211.             if(depth[i] <= (1 << j)) continue;
  212.             int u = f[i][j - 1].fi;
  213.             f[i][j].fi = f[u][j - 1].fi;
  214.             f[i][j].se = max(f[i][j - 1].se, f[u][j - 1].se);
  215.         }
  216.     }
  217.  
  218.     for(int i = 1; i <= m; i++) {
  219.         if(!used[i]) {
  220.             int id = ed[i].id;
  221.             int u = ed[i].u, v = ed[i].v;
  222.             int w = ed[i].w;
  223.             pii tmp = find_d(u, v);
  224.             ans[id] = tmp.se;
  225.             if(depth[u] < depth[v]) swap(u, v);
  226.             a[u].pb(w);
  227.             a[v].pb(w);
  228.             b[tmp.fi].pb(w);
  229.             b[tmp.fi].pb(w);
  230.         }
  231.     }
  232.  
  233.     dot(1, 0, 0);
  234.     for(int i = 1; i <= m; i++) {
  235.         if(used[i]) {
  236.             int u = ed[i].u, v = ed[i].v;
  237.             if(depth[u] < depth[v]) swap(u, v);
  238.             int id = ed[i].id;
  239.             ans[id] = dp[u];
  240.         }
  241.     }
  242.  
  243.     for(int i = 1; i <= m; i++) {
  244.         cout << ans[i] << '\n';
  245.     }
  246. }
  247.  
  248. int main()
  249. {
  250.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  251.     #ifndef ONLINE_JUDGE
  252.     freopen("input.txt", "r", stdin);
  253.     freopen("output.txt", "w", stdout);
  254.     #else
  255.     //online
  256.     #endif
  257.  
  258.     int tc = 1, ddd = 0;
  259.     // cin >> tc;
  260.     while(tc--) {
  261.         //ddd++;
  262.         //cout << "Case #" << ddd << ": ";
  263.         solve();
  264.     }
  265. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement