oj.uz

Submission #941

# Submission time Handle Problem Language Result Execution time Memory
941 2013-05-26T04:12:23 Z tncks0121 비용 (KOI11_cost) C++
24 / 24
 57 ms 3228 KB 
#include<stdio.h>
#include<algorithm>
 
#define V_ 100000
#define E_ 100000
#define INF 1000000000
typedef unsigned long long lld;
 
int V, E;
struct S1{
    int a, b, v;
    bool operator < (const S1 &t) const { return v > t.v; }
}G[E_+1];
 
int Sum [E_+1];
 
int group[V_+1], cnt[V_+1];
int find_group (int node){
    if(group[node] == node) return node;
    return group[node] = find_group(group[node]);
}
 
lld res;
 
int main(){
    int i, j;
 
    scanf("%d%d",&V,&E);
    for(i=1; i<=E; i++) scanf("%d%d%d",&G[i].a,&G[i].b,&G[i].v);
    std::sort(G+1, G+E+1);
     
    for(i=1; i<=V; i++) group[i] = i, cnt[i] = 1;
 
    Sum[E] = G[E].v;
    for(i=E-1; i>0; i--) Sum[i] = (Sum[i+1] + G[i].v)%INF;
 
    for(i=1; i<=E; i++){
        int a = find_group(G[i].a), b = find_group(G[i].b);
        if(a != b){
            res = (res + (lld)cnt[a] * cnt[b] * Sum[i]) % INF;
            cnt[a] += cnt[b]; group[b] = a; cnt[b] = 0;
        }
    }
 
    printf("%llu\n",res);
     
    return 0;
}

Subtask #1
4.8 / 4.8

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

Subtask #2
7.2 / 7.2

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3228 KB Output is correct
2 Correct 25 ms 3228 KB Output is correct
3 Correct 46 ms 3228 KB Output is correct
4 Correct 9 ms 3228 KB Output is correct
5 Correct 54 ms 3228 KB Output is correct
6 Correct 28 ms 3228 KB Output is correct
7 Correct 56 ms 3228 KB Output is correct
8 Correct 55 ms 3228 KB Output is correct
9 Correct 52 ms 3228 KB Output is correct
10 Correct 57 ms 3228 KB Output is correct