제출 #4942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4942		cki86201	비용 (KOI11_cost)	C++98	24 / 24	52 ms	2924 KiB

cost

#include<stdio.h>
#include<algorithm>
using namespace std;

const int MOD = 1e9;
typedef long long ll;

struct edge{
	int st,en,len;
	bool operator<(const edge &l)const{
		return len<l.len;
	}
}inp[100010];

int n, m;
ll ans;
ll now;

struct UnF{
	int p[100010];
	int w[100010];
	void init(){for(int i=0;i<n;i++)p[i] = i, w[i] = 1;}
	int Find(int x){
		if(p[x] == x)return x;
		return p[x] = Find(p[x]);
	}
	int Union(int x,int y){
		x = Find(x), y = Find(y);
		if(x==y)return (int)now;
		now -= (ll)w[x] * (w[x] - 1) / 2 + (ll)w[y] * (w[y] - 1) / 2;
		now += (ll)(w[x] + w[y]) * (w[x] + w[y] - 1) / 2;
		now %= MOD;
		if(w[x] > w[y])p[y] = x, w[x] += w[y];
		else p[x] = y, w[y] += w[x];
		return (int)now;
	}
};

int main()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i=0;i<m;i++)scanf("%d%d%d",&inp[i].st,&inp[i].en,&inp[i].len);
	sort(inp,inp+m);
	UnF uf;
	uf.init();
	for(i=m-1;i>=0;i--)ans += (ll)inp[i].len * uf.Union(inp[i].st, inp[i].en), ans %= MOD;
	printf("%lld",ans);
	return 0;
}

• Subtask 1: 4.8 / 4.8
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12