Submission #1171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171		kriii	비용 (KOI11_cost)	C++98	24 / 24	61 ms	3624 KiB

cost

#include <stdio.h>
#include <algorithm>

struct edge{int x,y; long long c;} E[100010];
bool cmp(const edge& a, const edge& b){return a.c > b.c;}

const long long mod = 1000000000;
int N,M,P[100010]; long long C[100010],CON,ANS;

int find(int x){return P[x] = (x == P[x]) ? x : find(P[x]);}

int main()
{
	int i,x,y;

	scanf ("%d %d",&N,&M);
	for (i=0;i<M;i++) scanf ("%d %d %lld",&E[i].x,&E[i].y,&E[i].c);
	std::sort(E,E+M,cmp);

	for (i=1;i<=N;i++){
		P[i] = i;
		C[i] = 1;
	}
	for (i=0;i<M;i++){
		x = find(E[i].x);
		y = find(E[i].y);

		if (x != y){
			P[y] = x;
			CON = (CON + C[x] * C[y]) % mod;
			C[x] += C[y];
		}

		ANS = (ANS + CON * E[i].c) % mod;
	}

	printf ("%lld",ANS);

	return 0;
}

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