Advertisement
Guest User

Untitled

a guest
Nov 11th, 2018
211
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define x first
  6. #define y second
  7. #define pb push_back
  8. #define mp make_pair
  9. #define sqr(a) ((a) * (a))
  10. #define sz(a) int((a).size())
  11. #define all(a) (a).begin(), (a).end()
  12. #define forn(i, n) for (int i = 0; i < int(n); ++i)
  13. #define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
  14.  
  15. template<class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
  16.     return out <<  "(" << a.x << ", " << a.y << ")";
  17. }
  18.  
  19. template<class A> ostream& operator << (ostream& out, const vector<A> &a) {
  20.     out << "[";
  21.     for (auto it = a.begin(); it != a.end(); ++it) {
  22.         if (it != a.begin())
  23.             out << ", ";
  24.         out << *it;
  25.     }
  26.     return out << "]";
  27. }
  28.  
  29. typedef long long li;
  30. typedef long double ld;
  31. typedef pair<int, int> pt;
  32.  
  33. const int INF = 1e9;
  34. const li INF64 = 1e18;
  35. const int MOD = 1e9 + 7;
  36. const ld PI = acosl(-1.0);
  37. const ld EPS = 1e-9;
  38.  
  39. mt19937 rnd(time(NULL));
  40. mt19937_64 rnd64(time(NULL));
  41.  
  42. const int N = 100 * 1000 + 13;
  43. const int M = 1000 * 1000 + 13;
  44. const int LOGN = 19;
  45.  
  46. int n, m;
  47. pair<pt, pt> e[M];
  48. vector<pt> g[N];
  49.  
  50. bool read() {
  51.     if (scanf("%d%d", &n, &m) != 2)
  52.         return false;
  53.     forn(i, n)
  54.         g[i].clear();
  55.     forn(i, m){
  56.         scanf("%d%d%d", &e[i].y.x, &e[i].y.y, &e[i].x.x);
  57.         --e[i].y.x, --e[i].y.y;
  58.         e[i].x.y = i;
  59.     }
  60.     return true;
  61. }
  62.  
  63. int up[N][LOGN];
  64. int mx[N][LOGN], mn[N][LOGN];
  65.  
  66. int rk[N], p[N];
  67.  
  68. int getP(int a){
  69.     return (a == p[a] ? a : p[a] = getP(p[a]));
  70. }
  71.  
  72. bool merge(int a, int b){
  73.     a = getP(a);
  74.     b = getP(b);
  75.    
  76.     if (a == b)
  77.         return false;
  78.    
  79.     if (rk[b] > rk[a])
  80.         swap(a, b);
  81.    
  82.     rk[a] += rk[b];
  83.     p[b] = a;
  84.    
  85.     return true;
  86. }
  87.  
  88. int h[N];
  89.  
  90. void dfs(int v, int p = -1){
  91.     for (auto it : g[v]){
  92.         int u = it.x;
  93.         if (u == p) continue;
  94.        
  95.         up[u][0] = v;
  96.         mx[u][0] = it.y;
  97.         fore(i, 1, LOGN){
  98.             up[u][i] = up[up[u][i - 1]][i - 1];
  99.             mx[u][i] = max(mx[u][i - 1], mx[up[u][i - 1]][i - 1]);
  100.         }
  101.         h[u] = h[v] + 1;
  102.        
  103.         dfs(u, v);
  104.     }
  105. }
  106.  
  107. int lca(int v, int u, int& l){
  108.     int res = -INF;
  109.    
  110.     if (h[u] > h[v])
  111.         swap(v, u);
  112.    
  113.     for (int i = LOGN - 1; i >= 0; --i){
  114.         if (h[up[v][i]] >= h[u]){
  115.             res = max(res, mx[v][i]);
  116.             v = up[v][i];
  117.         }
  118.     }
  119.    
  120.     if (v == u){
  121.         l = v;
  122.         return res;
  123.     }
  124.    
  125.     for (int i = LOGN - 1; i >= 0; --i){
  126.         if (up[v][i] != up[u][i]){
  127.             res = max(res, mx[v][i]);
  128.             res = max(res, mx[u][i]);
  129.             v = up[v][i];
  130.             u = up[u][i];
  131.         }
  132.     }
  133.    
  134.     l = up[v][0];
  135.     res = max(res, mx[v][0]);
  136.     res = max(res, mx[u][0]);
  137.    
  138.     return res;
  139. }
  140.  
  141. void upd(int v, int u, int val){
  142.     if (v == u) return;
  143.     for (int i = LOGN - 1; i >= 0; --i){
  144.         if (h[up[v][i]] >= h[u]){
  145.             mn[v][i] = min(mn[v][i], val);
  146.             v = up[v][i];
  147.             if (v == u) break;
  148.         }
  149.     }
  150. }
  151.  
  152. int ans[M];
  153.  
  154. void solve() {
  155.     memset(ans, -1, sizeof(ans));
  156.    
  157.     sort(e, e + m);
  158.     forn(i, n) rk[i] = 1, p[i] = i;
  159.    
  160.     vector<int> mst, notmst;
  161.    
  162.     forn(i, m){
  163.         if (merge(e[i].y.x, e[i].y.y)){
  164.             mst.pb(i);
  165.             g[e[i].y.x].pb(mp(e[i].y.y, e[i].x.x));
  166.             g[e[i].y.y].pb(mp(e[i].y.x, e[i].x.x));
  167.         }
  168.         else{
  169.             notmst.pb(i);
  170.         }
  171.     }
  172.    
  173.     forn(i, n) forn(j, LOGN)
  174.         mx[i][j] = -INF;
  175.    
  176.     dfs(0);
  177.    
  178.     forn(i, n) forn(j, LOGN)
  179.         mn[i][j] = INF;
  180.    
  181.     for (auto it : notmst){
  182.         int v = e[it].y.x;
  183.         int u = e[it].y.y;
  184.         int l;
  185.         int res = lca(v, u, l);
  186.         ans[e[it].x.y] = res;
  187.         upd(v, l, e[it].x.x);
  188.         upd(u, l, e[it].x.x);
  189.     }
  190.    
  191.     for (int j = LOGN - 1; j > 0; --j){
  192.         forn(i, n){
  193.             mn[i][j - 1] = min(mn[i][j - 1], mn[i][j]);
  194.             mn[up[i][j - 1]][j - 1] = min(mn[up[i][j - 1]][j - 1], mn[i][j]);
  195.         }
  196.     }
  197.    
  198.     for (auto it : mst){
  199.         int v = e[it].y.x;
  200.         int u = e[it].y.y;
  201.         if (h[v] < h[u]) swap(v, u);
  202.         ans[e[it].x.y] = mn[v][0];
  203.     }
  204.    
  205.     forn(i, m)
  206.         printf("%d\n", ans[i]);
  207. }
  208.  
  209. int main() {
  210. #ifdef _DEBUG
  211.     freopen("input.txt", "r", stdin);
  212.     //freopen("output.txt", "w", stdout);
  213.    
  214.     int tt = clock();
  215. #endif
  216.  
  217.     cout << fixed << setprecision(10);
  218.     cerr << fixed << setprecision(10);
  219.  
  220. #ifdef _DEBUG
  221.     while (read()) {
  222. #else
  223.     if (read()) {
  224. #endif
  225.         solve();
  226.        
  227. #ifdef _DEBUG
  228.         cerr << "TIME = " << clock() - tt << endl;
  229.         tt = clock();  
  230. #endif
  231.     }
  232. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement