Submission #1668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1668		solveit	비용 (KOI11_cost)	C++98	24 / 24	68 ms	3332 KiB

cost

#include <iostream> 
#include <math.h> 
#include <algorithm> 
  
using namespace std; 
  
#define MOD 1000000000
#define ll long long  

int N, M, p[100005], s[100005];
pair<int,pair<int,int> > g[100005];
ll res = 0, curr = 0;

ll C(int n) {return ((ll)n)*(n-1)/2;}

int find(int n) {
    if(p[n] == 0) return n;
    return p[n] = find(p[n]);
}

void make_union(int n1, int n2, int w) {
    int p1 = find(n1), p2 = find(n2);
    if(p1 == p2) {
        res += w*curr;
        res %= MOD;
        return;
    }
    curr -= C(s[p1])+C(s[p2]);
    curr += C(s[p1]+s[p2]);
    if(p1<p2) {
        p[p2] = p1;
        s[p1] += s[p2];
    }    
    else {
        p[p1] = p2;
        s[p2] += s[p1];
    }
    res += w*curr;
    res %= MOD;
}

int main() { 
    scanf("%d %d",&N,&M);
    fill(s,s+1+N,1);
    for(int i = 1;i<=M;++i) {
        int n1, n2, w;
        scanf("%d %d %d",&n1,&n2,&w);
        g[i] = make_pair(w,make_pair(n1,n2));
    }
    sort(g+1,g+1+M);
    for(int i = M;i>=1;--i) {
        make_union(g[i].second.first,g[i].second.second,g[i].first);
    }
    printf("%lld\n",res);
    return 0; 
} 

• Subtask 1: 4.8 / 4.8
• Subtask 2: 7.2 / 7.2
• Subtask 3: 12 / 12