oj.uz

Submission #1171

# Submission time Handle Problem Language Result Execution time Memory
1171 2013-06-28T14:00:23 Z kriii 비용 (KOI11_cost) C++
24 / 24
 61 ms 3624 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3624 KB Output is correct
2 Correct 0 ms 3624 KB Output is correct
3 Correct 0 ms 3624 KB Output is correct
4 Correct 0 ms 3624 KB Output is correct

Subtask #2
7.2 / 7.2

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3624 KB Output is correct
2 Correct 0 ms 3624 KB Output is correct
3 Correct 0 ms 3624 KB Output is correct
4 Correct 0 ms 3624 KB Output is correct
5 Correct 2 ms 3624 KB Output is correct
6 Correct 3 ms 3624 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3624 KB Output is correct
2 Correct 26 ms 3624 KB Output is correct
3 Correct 58 ms 3624 KB Output is correct
4 Correct 11 ms 3624 KB Output is correct
5 Correct 60 ms 3624 KB Output is correct
6 Correct 25 ms 3624 KB Output is correct
7 Correct 56 ms 3624 KB Output is correct
8 Correct 61 ms 3624 KB Output is correct
9 Correct 54 ms 3624 KB Output is correct
10 Correct 58 ms 3624 KB Output is correct