# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
5370 |
2014-04-16T08:12:42 Z |
baneling100 |
비용 (KOI11_cost) |
C++ |
|
52 ms |
3040 KB |
#include <stdio.h>
#include <algorithm>
using namespace std;
typedef pair <int,int> ppair;
pair <int,ppair> road[100001];
int n, m, anc[100001], cnt[100001];
long long ans, hab;
void input(void)
{
int i, x, y, w;
scanf("%d %d",&n,&m);
for(i=1 ; i<=m ; i++)
{
scanf("%d %d %d",&x,&y,&w);
hab+=w;
road[i]=make_pair(w,make_pair(x,y));
}
sort(road+1,road+m+1);
for(i=1 ; i<=n ; i++)
cnt[i]=1;
}
int find_anc(int x)
{
while(anc[x]>0)
{
x=anc[x];
}
return x;
}
void process(void)
{
int i, a1, a2;
for(i=m ; i>=1 ; i--)
{
a1=find_anc(road[i].second.first);
a2=find_anc(road[i].second.second);
if(a1!=a2)
{
ans+=(long long)cnt[a1]*(long long)cnt[a2]*hab;
ans%=1000000000;
if(a1<a2)
{
anc[a2]=a1;
cnt[a1]+=cnt[a2];
}
else
{
anc[a1]=a2;
cnt[a2]+=cnt[a1];
}
}
hab-=road[i].first;
}
}
void output(void)
{
printf("%lld",ans);
}
int main(void)
{
input();
process();
output();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
3040 KB |
Output is correct |
2 |
Correct |
0 ms |
3040 KB |
Output is correct |
3 |
Correct |
0 ms |
3040 KB |
Output is correct |
4 |
Correct |
0 ms |
3040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
3040 KB |
Output is correct |
2 |
Correct |
0 ms |
3040 KB |
Output is correct |
3 |
Correct |
0 ms |
3040 KB |
Output is correct |
4 |
Correct |
0 ms |
3040 KB |
Output is correct |
5 |
Correct |
0 ms |
3040 KB |
Output is correct |
6 |
Correct |
4 ms |
3040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
3040 KB |
Output is correct |
2 |
Correct |
20 ms |
3040 KB |
Output is correct |
3 |
Correct |
48 ms |
3040 KB |
Output is correct |
4 |
Correct |
8 ms |
3040 KB |
Output is correct |
5 |
Correct |
44 ms |
3040 KB |
Output is correct |
6 |
Correct |
24 ms |
3040 KB |
Output is correct |
7 |
Correct |
52 ms |
3040 KB |
Output is correct |
8 |
Correct |
48 ms |
3040 KB |
Output is correct |
9 |
Correct |
36 ms |
3040 KB |
Output is correct |
10 |
Correct |
48 ms |
3040 KB |
Output is correct |