提出 #58292961

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;


template<class Abel> struct WeightedUnionFind {
     vector<int> par;
     vector<int> rank;
     vector<Abel> diff_weight;
 
     WeightedUnionFind(int n = 1, Abel SUM_UNITY = 0) {
         init(n, SUM_UNITY);
     }
 
     void init(int n = 1, Abel SUM_UNITY = 0) {
         par.resize(n); rank.resize(n); diff_weight.resize(n);
         for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
     }
 
     int root(int x) {
         if (par[x] == x) {
             return x;
         }
         else {
             int r = root(par[x]);
             diff_weight[x] += diff_weight[par[x]];
             return par[x] = r;
         }
     }
 
     Abel weight(int x) {
         root(x);
         return diff_weight[x];
     }
 
     bool issame(int x, int y) {
         return root(x) == root(y);
     }
 
     bool merge(int x, int y, Abel w) {
         w += weight(x); w -= weight(y);
         x = root(x); y = root(y);
         if (x == y) return false;
         if (rank[x] < rank[y]) swap(x, y), w = -w;
         if (rank[x] == rank[y]) ++rank[x];
         par[y] = x;
         diff_weight[y] = w;
         return true;
     }
 
     Abel diff(int x, int y) {
         return weight(y) - weight(x);
     }
 };

int main(){
	int n,m;cin >> n >> m;
	WeightedUnionFind<long long>uf(n);
	for(int i = 0;i<m;i++){
		int u,v;
		long long w;
		cin >> u >> v >> w;
		u--,v--;
		uf.merge(u,v,w);
	}
	for(int i = 0;i<n;i++){
		cout << uf.weight(i) << " ";
	}
	cout << endl;
	return 0;
}

提出情報

ジャッジ結果