oj.uz

Submission #7883

# Submission time Handle Problem Language Result Execution time Memory
7883 2014-08-22T14:37:54 Z gs14004 비용 (KOI11_cost) C++
24 / 24
 60 ms 4216 KB 
#include <cstdio>
#include <algorithm>
using namespace std;

struct edge{int s,e,x;}a[100005];
int cmp(edge a, edge b){return a.x > b.x;}

int p[100005],r[100005],sz[100005],n,m;
long long sum[100005];
void init(){
    for (int i=1; i<=n; i++) p[i] = i, sz[i] = 1;
}

int fnd(int x){
    if(p[x] == x) return x;
    else return p[x] = fnd(p[x]);
}

void uni(int x, int y){
    x = fnd(x);
    y = fnd(y);
    if(r[x] > r[y]) p[x] = y, sz[y] += sz[x];
    else p[y] = x, sz[x] += sz[y];
    if(r[x] == r[y]) r[y]++;
}

int main(){
    scanf("%d %d",&n,&m);
    for (int i=0; i<m; i++) {
        scanf("%d %d %d",&a[i].s,&a[i].e,&a[i].x);
    }
    sort(a,a+m,cmp);
    init();
    sum[0] = a[0].x;
    for (int i=1; i<=m; i++) {
        sum[i] = sum[i-1] + a[i].x;
    }
    long long res = 0;
    for (int i=0; i<m; i++) {
        if(fnd(a[i].s) == fnd(a[i].e)) continue;
        else{
            res += (sum[m] - (i?sum[i-1]:0))*sz[fnd(a[i].s)] * sz[fnd(a[i].e)];
            uni(a[i].s,a[i].e);
        }
        res %= 1000000000;
    }
    printf("%lld",res);
}

Subtask #1
4.8 / 4.8

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

Subtask #2
7.2 / 7.2

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4216 KB Output is correct
2 Correct 28 ms 4216 KB Output is correct
3 Correct 40 ms 4216 KB Output is correct
4 Correct 8 ms 4216 KB Output is correct
5 Correct 52 ms 4216 KB Output is correct
6 Correct 28 ms 4216 KB Output is correct
7 Correct 52 ms 4216 KB Output is correct
8 Correct 52 ms 4216 KB Output is correct
9 Correct 60 ms 4216 KB Output is correct
10 Correct 52 ms 4216 KB Output is correct