oj.uz

Submission #16248

# Submission time Handle Problem Language Result Execution time Memory
16248 2015-08-18T11:23:01 Z eaststar 비용 (KOI11_cost) C++14
24 / 24
 64 ms 3036 KB 
#include <cstdio>
#include <algorithm>
struct data{
    int x,y,w;
    bool operator<(const data&r)const{
        return w>r.w;
    }
}path[100010];
int g[100010],cnt[100010],n;
long long int ans,w;
int seek(int nod){
    if(g[nod]==nod)return nod;
    return g[nod]=seek(g[nod]);
}
void merge(int a,int b){
    a=seek(a);
    b=seek(b);
    if(a==b)
    {
        ++n;
        return;
    }
    ans+=w*cnt[a]*cnt[b];
    g[b]=a;
    cnt[a]+=cnt[b];
}
int main(){
    int i,m,t;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i){
        scanf("%d%d%d",&path[i].x,&path[i].y,&path[i].w);
        w+=path[i].w;
    }
    std::sort(&path[1],&path[m+1]);
    for(i=1;i<=n;++i)g[i]=i,cnt[i]=1;
    for(i=1;i<n&&i<=m;++i){
        merge(path[i].x,path[i].y);
        w-=path[i].w;
        ans%=1000000000;
    }
    printf("%d",ans);
    return 0;
}

Subtask #1
4.8 / 4.8

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3036 KB Output is correct
2 Correct 0 ms 3036 KB Output is correct
3 Correct 0 ms 3036 KB Output is correct
4 Correct 0 ms 3036 KB Output is correct

Subtask #2
7.2 / 7.2

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3036 KB Output is correct
2 Correct 0 ms 3036 KB Output is correct
3 Correct 0 ms 3036 KB Output is correct
4 Correct 0 ms 3036 KB Output is correct
5 Correct 0 ms 3036 KB Output is correct
6 Correct 5 ms 3036 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3036 KB Output is correct
2 Correct 30 ms 3036 KB Output is correct
3 Correct 48 ms 3036 KB Output is correct
4 Correct 0 ms 3036 KB Output is correct
5 Correct 64 ms 3036 KB Output is correct
6 Correct 30 ms 3036 KB Output is correct
7 Correct 43 ms 3036 KB Output is correct
8 Correct 64 ms 3036 KB Output is correct
9 Correct 56 ms 3036 KB Output is correct
10 Correct 51 ms 3036 KB Output is correct