CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:Juho
Submission time:2021-10-07 16:57:00
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s2, 3details
#3ACCEPTED0.24 s3details

Code

#include <bits/stdc++.h>
using namespace std;

long n, a, b, c, vastaus;
vector<pair<long, pair<long, long>>> v;
long koko[200001], edustaja[200001];

int main() {
    cin>>n;
    for(long i=0;i<n-1;i++){
        cin>>a>>b>>c;
        v.push_back({c, {a,b}});
        
        edustaja[i+1]=i+1;
        koko[i+1]=1;
    }
    edustaja[n]=n;
    koko[n]=1;
    sort(v.begin(), v.end());
    
    for(long i=n-2;i>=0;i--){
        a=v[i].second.first;
        b=v[i].second.second;
        while(a!=edustaja[a]){
            a = edustaja[a];
        }
        while(b!=edustaja[b]){
            b = edustaja[b];
        }
        vastaus += v[i].first*koko[a]*koko[b];
        if(koko[a]>koko[b]){
            edustaja[b]=a;
            koko[a] += koko[b];
        }else{
            edustaja[a]=b;
            koko[b] += koko[a];
        }
    }
    cout<<vastaus;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict: ACCEPTED

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
1103702320243776

Test 3

Group: 3

Verdict: ACCEPTED

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
1080549209850010931