# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
145548 | 2019-08-20T11:28:45 Z | surface03 | 비용 (KOI11_cost) | C++14 | 57 ms | 4088 KB |
#include<bits/stdc++.h> using namespace std; using LL=long long; const LL MOD=(int)1e9; const int LM=(int)1e5+1; int N,M,G[LM],cnt[LM]; LL sum,ans; struct data{ int s,e,w; bool operator<(const data&r)const{ return w>r.w; } }A[LM]; void input(){ scanf("%d%d",&N,&M); for(int i=1;i<=N;i++){ G[i]=i; cnt[i]=1; } for(int i=0;i<M;i++){ scanf("%d%d%d",&A[i].s,&A[i].e,&A[i].w); sum+=A[i].w; } sort(A,A+M); } int Find(int n){ if(G[n]==n)return n; return G[n]=Find(G[n]); } void Union(int s,int e){ s=Find(s),e=Find(e); if(s==e)return; ans=(ans+sum*cnt[s]*cnt[e])%MOD; G[s]=e; cnt[e]+=cnt[s]; } int main(){ input(); for(int i=0;i<M;i++){ Union(A[i].s,A[i].e); sum-=A[i].w; } printf("%lld\n",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 2 ms | 504 KB | Output is correct |
3 | Correct | 2 ms | 376 KB | Output is correct |
4 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
2 | Correct | 16 ms | 504 KB | Output is correct |
3 | Correct | 3 ms | 376 KB | Output is correct |
4 | Correct | 3 ms | 376 KB | Output is correct |
5 | Correct | 4 ms | 504 KB | Output is correct |
6 | Correct | 7 ms | 636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 888 KB | Output is correct |
2 | Correct | 25 ms | 1784 KB | Output is correct |
3 | Correct | 51 ms | 3148 KB | Output is correct |
4 | Correct | 12 ms | 1016 KB | Output is correct |
5 | Correct | 52 ms | 3448 KB | Output is correct |
6 | Correct | 28 ms | 2168 KB | Output is correct |
7 | Correct | 54 ms | 3704 KB | Output is correct |
8 | Correct | 50 ms | 3960 KB | Output is correct |
9 | Correct | 57 ms | 3964 KB | Output is correct |
10 | Correct | 54 ms | 4088 KB | Output is correct |