# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1668 |
2013-07-11T23:11:07 Z |
solveit |
비용 (KOI11_cost) |
C++ |
|
68 ms |
3332 KB |
#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
#define MOD 1000000000
#define ll long long
int N, M, p[100005], s[100005];
pair<int,pair<int,int> > g[100005];
ll res = 0, curr = 0;
ll C(int n) {return ((ll)n)*(n-1)/2;}
int find(int n) {
if(p[n] == 0) return n;
return p[n] = find(p[n]);
}
void make_union(int n1, int n2, int w) {
int p1 = find(n1), p2 = find(n2);
if(p1 == p2) {
res += w*curr;
res %= MOD;
return;
}
curr -= C(s[p1])+C(s[p2]);
curr += C(s[p1]+s[p2]);
if(p1<p2) {
p[p2] = p1;
s[p1] += s[p2];
}
else {
p[p1] = p2;
s[p2] += s[p1];
}
res += w*curr;
res %= MOD;
}
int main() {
scanf("%d %d",&N,&M);
fill(s,s+1+N,1);
for(int i = 1;i<=M;++i) {
int n1, n2, w;
scanf("%d %d %d",&n1,&n2,&w);
g[i] = make_pair(w,make_pair(n1,n2));
}
sort(g+1,g+1+M);
for(int i = M;i>=1;--i) {
make_union(g[i].second.first,g[i].second.second,g[i].first);
}
printf("%lld\n",res);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
3332 KB |
Output is correct |
2 |
Correct |
0 ms |
3332 KB |
Output is correct |
3 |
Correct |
0 ms |
3332 KB |
Output is correct |
4 |
Correct |
0 ms |
3332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
3332 KB |
Output is correct |
2 |
Correct |
0 ms |
3332 KB |
Output is correct |
3 |
Correct |
1 ms |
3332 KB |
Output is correct |
4 |
Correct |
0 ms |
3332 KB |
Output is correct |
5 |
Correct |
1 ms |
3332 KB |
Output is correct |
6 |
Correct |
5 ms |
3332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
3332 KB |
Output is correct |
2 |
Correct |
27 ms |
3332 KB |
Output is correct |
3 |
Correct |
58 ms |
3332 KB |
Output is correct |
4 |
Correct |
9 ms |
3332 KB |
Output is correct |
5 |
Correct |
63 ms |
3332 KB |
Output is correct |
6 |
Correct |
29 ms |
3332 KB |
Output is correct |
7 |
Correct |
64 ms |
3332 KB |
Output is correct |
8 |
Correct |
64 ms |
3332 KB |
Output is correct |
9 |
Correct |
68 ms |
3332 KB |
Output is correct |
10 |
Correct |
63 ms |
3332 KB |
Output is correct |