| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4919 |
2014-01-09T12:24:43 Z |
gs13068 |
비용 (KOI11_cost) |
C++ |
|
48 ms |
3432 KB |
#include<cstdio>
#include<algorithm>
int parent[100001];
int height[100001];
int size[100001];
int res;
int root(int x){return x==parent[x]?x:parent[x]=root(parent[x]);}
inline void combine(int a,int b,int c)
{
a=root(a);
b=root(b);
if(a==b)(res+=size[a]*(size[a]-1)/2*c)%=1000000000;
else if(a!=b)
{
(res+=(size[a]+size[b])*(size[a]+size[b]-1)/2*c)%=1000000000;
if(height[a]<height[b])
{
parent[a]=b;
size[b]+=size[a];
}
else
{
parent[b]=a;
size[a]+=size[b];
}
if(height[a]==height[b])
height[a]++;
}
}
struct edge
{
int s;
int e;
int t;
} a[100000];
inline bool operator <(const edge &x,const edge &y)
{
return x.t>y.t;
}
int main()
{
int i,n,m;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
parent[i]=i;
size[i]=1;
}
for(i=0;i<m;i++)scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].t);
std::sort(a,a+m);
for(i=0;i<m;i++)combine(a[i].s,a[i].e,a[i].t);
printf("%d\n",res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
3432 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| 5 |
Incorrect |
0 ms |
3432 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
3432 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3432 KB |
Output isn't correct |
| 2 |
Incorrect |
20 ms |
3432 KB |
Output isn't correct |
| 3 |
Incorrect |
44 ms |
3432 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
3432 KB |
Output isn't correct |
| 5 |
Incorrect |
40 ms |
3432 KB |
Output isn't correct |
| 6 |
Incorrect |
24 ms |
3432 KB |
Output isn't correct |
| 7 |
Incorrect |
40 ms |
3432 KB |
Output isn't correct |
| 8 |
Incorrect |
44 ms |
3432 KB |
Output isn't correct |
| 9 |
Incorrect |
48 ms |
3432 KB |
Output isn't correct |
| 10 |
Incorrect |
48 ms |
3432 KB |
Output isn't correct |
