Submission #22617

#	Time	Username	Problem	Language	Result	Execution time	Memory
22617		AcornCkiGs14004Team (#40)	Logistical Metropolis (KRIII5_LM)	C++11	2 / 7	79 ms	2060 KiB

LM

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;

const int MAXN = 1005;
struct disj{
	int pa[MAXN], sz[MAXN];
	void init(int n){
		for(int i=0; i<=n; i++){
			pa[i] = i;
			sz[i] = 1;
		}
	}
	int find(int x){
		return pa[x] = (pa[x] == x ? x : find(pa[x]));
	}
	bool uni(int p, int q){
		p = find(p);
		q = find(q);
		if(p == q) return 0;
		pa[q] = p;
		sz[p] += sz[q];
		return 1;
	}
}disj;

struct edg{int s, e, x;}e[3005];

int n, m;

int main(){
	cin >> n >> m;
	for(int i=0; i<m; i++){
		cin >> e[i].s >> e[i].e >> e[i].x;
	}
	sort(e, e+m, [&](const edg &a, const edg &b){
		return a.x < b.x;
	});
	for(int i=1; i<=n; i++){
		int ans = 0;
		disj.init(n);
		for(int j=0; j<m; j++){
			if(e[j].s == i || e[j].e == i){
				if(disj.uni(e[j].s, e[j].e)){
				ans += e[j].x;
				}
			}
		}
		for(int j=0; j<m; j++){
			if(disj.uni(e[j].s, e[j].e)) ans += e[j].x;
		}
		cout << ans << endl;
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5