| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1170 |
2013-06-28T13:58:34 Z |
kriii |
비용 (KOI11_cost) |
C++ |
|
64 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 = 1000000009;
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;
}
| # |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3624 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
3624 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
3624 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
3624 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
3624 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
3624 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
3624 KB |
Output isn't correct |
| 2 |
Incorrect |
26 ms |
3624 KB |
Output isn't correct |
| 3 |
Incorrect |
53 ms |
3624 KB |
Output isn't correct |
| 4 |
Incorrect |
7 ms |
3624 KB |
Output isn't correct |
| 5 |
Incorrect |
57 ms |
3624 KB |
Output isn't correct |
| 6 |
Incorrect |
28 ms |
3624 KB |
Output isn't correct |
| 7 |
Incorrect |
60 ms |
3624 KB |
Output isn't correct |
| 8 |
Incorrect |
64 ms |
3624 KB |
Output isn't correct |
| 9 |
Incorrect |
58 ms |
3624 KB |
Output isn't correct |
| 10 |
Incorrect |
63 ms |
3624 KB |
Output isn't correct |
