oj.uz

Submission #1668

# Submission time Handle Problem Language Result Execution time Memory
1668 2013-07-11T23:11:07 Z solveit 비용 (KOI11_cost) C++
24 / 24
 68 ms 3332 KB 
#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

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

Subtask #2
7.2 / 7.2

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3332 KB Output is correct
2 Correct 27 ms 3332 KB Output is correct
3 Correct 58 ms 3332 KB Output is correct
4 Correct 9 ms 3332 KB Output is correct
5 Correct 63 ms 3332 KB Output is correct
6 Correct 29 ms 3332 KB Output is correct
7 Correct 64 ms 3332 KB Output is correct
8 Correct 64 ms 3332 KB Output is correct
9 Correct 68 ms 3332 KB Output is correct
10 Correct 63 ms 3332 KB Output is correct