fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define endl '\n'
  4. #define MASK(n) (1LL << n)
  5. #define PhTrNghia "COLDWAR"
  6.  
  7. using namespace std;
  8.  
  9. const int maxn = 2e5 + 5;
  10. const int inf = 1e18;
  11.  
  12. struct segtree{
  13.     struct node{
  14.         int mn, lazy;
  15.         node(){
  16.             mn = inf;
  17.             lazy = inf;
  18.         }
  19.     };
  20.     int n;
  21.     vector <node> tree;
  22.  
  23.     segtree(int _n){
  24.         n = _n;
  25.         tree.assign(n << 2 | 3, node());
  26.     }
  27.  
  28.     void push_down(int id){
  29.         if (tree[id].lazy != inf){
  30.             tree[id << 1].lazy = min(tree[id << 1].lazy, tree[id].lazy);
  31.             tree[id << 1 | 1].lazy = min(tree[id << 1 | 1].lazy, tree[id].lazy);
  32.             tree[id << 1].mn = min(tree[id << 1].mn, tree[id].lazy);
  33.             tree[id << 1 | 1].mn = min(tree[id << 1 | 1].mn, tree[id].lazy);
  34.             tree[id].lazy = inf;
  35.         }
  36.     }
  37.  
  38.     void update(int id, int l, int r, int u, int v, int w){
  39.         if (l > v || r < u) return;
  40.         if (l >= u && r <= v){
  41.             tree[id].mn = min(tree[id].mn, w);
  42.             tree[id].lazy = min(tree[id].lazy, w);
  43.             return;
  44.         }
  45.         int mid = (l + r) >> 1;
  46.         push_down(id);
  47.         update(id << 1, l, mid, u, v, w);
  48.         update(id << 1 | 1, mid + 1, r, u, v, w);
  49.         tree[id].mn = min(tree[id << 1].mn, tree[id << 1 | 1].mn);
  50.     }
  51.  
  52.     int get(int id, int l, int r, int pos){
  53.         if (l > pos || r < pos) return inf;
  54.         if (l == r) return tree[id].mn;
  55.         int mid = (l + r) >> 1;
  56.         push_down(id);
  57.         int get1 = get(id << 1, l, mid, pos);
  58.         int get2 = get(id << 1 | 1, mid + 1, r, pos);
  59.         return min(get1, get2);
  60.     }
  61.  
  62.     void update(int l, int r, int val){
  63.         update(1, 1, n, l, r, val);
  64.     }
  65.  
  66.     int get(int pos){
  67.         return get(1, 1, n, pos);
  68.     }
  69. };
  70.  
  71. struct DSU{
  72.     int n;
  73.     vector <int> parent, sz;
  74.     DSU(int _n){
  75.         n = _n;
  76.         parent.assign(n + 5, 0);
  77.         sz.assign(n + 5, 0);
  78.         for (int i = 1; i <= n; i++){
  79.             sz[i] = 1;
  80.             parent[i] = i;
  81.         }
  82.     }
  83.  
  84.     int find_parent(int u){
  85.         if (u == parent[u]) return u;
  86.         return parent[u] = find_parent(parent[u]);
  87.     }
  88.  
  89.     bool Union(int x, int y){
  90.         x = find_parent(x);
  91.         y = find_parent(y);
  92.         if (x == y) return 0;
  93.         if (sz[x] < sz[y]) swap(x, y);
  94.         sz[x] += sz[y];
  95.         parent[y] = x;
  96.         return 1;
  97.     }
  98. };
  99.  
  100. struct phtrnghia{
  101.     int x, y, w, id;
  102. };
  103.  
  104. bool cmp(phtrnghia a, phtrnghia b){
  105.     return a.w < b.w;
  106. }
  107.  
  108. int n, m, MST_weight = 0, timer_dfs = 0;
  109. vector <int> g[maxn];
  110. vector <phtrnghia> edges, tmp;
  111. bool visited[maxn];
  112.  
  113. void kruskal(){
  114.     sort(tmp.begin(), tmp.end(), cmp);
  115.     DSU dsu(n);
  116.     int cnt = 0;
  117.     for (phtrnghia cur: tmp){
  118.         int x = cur.x;
  119.         int y = cur.y;
  120.         int w = cur.w;
  121.         int id = cur.id;
  122.         if (dsu.Union(x, y)){
  123.             visited[id] = 1;
  124.             cnt++;
  125.             g[x].push_back(y);
  126.             g[y].push_back(x);
  127.             MST_weight += w;
  128.         }
  129.         if (cnt == n-1) return;
  130.     }
  131. }
  132.  
  133. int sz[maxn], bigC[maxn], parent[maxn], head[maxn], dep[maxn], op[maxn];
  134.  
  135. void pre_dfs(int u, int p){
  136.     sz[u] = 1;
  137.     dep[u] = dep[p] + 1;
  138.     parent[u] = p;
  139.     op[u] = ++timer_dfs;
  140.     for (int v: g[u]){
  141.         if (v == p) continue;
  142.         pre_dfs(v, u);
  143.         sz[u] += sz[v];
  144.         if (sz[bigC[u]] < sz[v]) bigC[u] = v;
  145.     }
  146. }
  147.  
  148. void dfs(int u, int p, int top){
  149.     head[u] = top;
  150.  
  151.     if (bigC[u]) dfs(bigC[u], u, top);
  152.  
  153.     for (int v: g[u]){
  154.         if (v == p or v == bigC[u]) continue;
  155.         dfs(v, u, v);
  156.     }
  157. }
  158.  
  159. segtree smt(maxn);
  160.  
  161. void hld_update(int u, int v, int w){
  162.     while (head[u] != head[v]){
  163.         if (dep[head[u]] < dep[head[v]]) swap(u, v);
  164.         smt.update(op[head[u]], op[u], w);
  165.         u = parent[head[u]];
  166.     }
  167.     if (dep[u] > dep[v]) swap(u, v);
  168.     if (op[u] + 1 <= op[v]) smt.update(op[u] + 1, op[v], w);
  169. }
  170.  
  171. int hld_get(int u){
  172.     return smt.get(op[u]);
  173. }
  174.  
  175. signed main(){
  176.     ios_base::sync_with_stdio(false);
  177.     cin.tie(0); cout.tie(0);
  178.     if (fopen(PhTrNghia".INP", "r")){
  179.         freopen(PhTrNghia".INP", "r", stdin);
  180.         freopen(PhTrNghia".OUT", "w", stdout);
  181.     }
  182.  
  183.     cin >> n >> m;
  184.     for (int i = 1; i <= m; i++){
  185.         int x, y, w;
  186.         cin >> x >> y >> w;
  187.         edges.push_back({x, y, w, i});
  188.         tmp.push_back({x, y, w, i});
  189.     }
  190.  
  191.     kruskal();
  192.     pre_dfs(1, 0);
  193.     dfs(1, 0, 1);
  194.  
  195.     for (phtrnghia cur: edges){
  196.         int x = cur.x;
  197.         int y = cur.y;
  198.         int w = cur.w;
  199.         int id = cur.id;
  200.         if (!visited[id]) hld_update(x, y, w);
  201.     }
  202.  
  203.     for (phtrnghia cur: edges){
  204.         int x = cur.x;
  205.         int y = cur.y;
  206.         int w = cur.w;
  207.         int id = cur.id;
  208.         if (dep[x] > dep[y]) swap(x, y);
  209.         int res;
  210.         if (visited[id]){
  211.             res = hld_get(y);
  212.             if (res == inf) res = -1; 
  213.             if (res != -1) res = MST_weight - w + res;
  214.         } else res = MST_weight;
  215.         cout << res << endl;
  216.     }
  217.     return 0;
  218. }
  219. /*
  220.  
  221. */
Success #stdin #stdout 0.01s 27804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Zige45
language:
C++14 (gcc 8.3)
created:
21 hours 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!