Submission #943

#	Time	Username	Problem	Language	Result	Execution time	Memory
943		testtest	비용 (KOI11_cost)	C++98	24 / 24	52 ms	3432 KiB

cost

#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
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12