CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:xyrj
Submission time:2021-10-13 22:55:26
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.23 s3details

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int edustaja(int verkko[], int a)
{
    // cout << "Edustajaa solmulle " << a << "\n";
    // cout << "    " << verkko[a] << "\n";
    while (a != verkko[a])
        a = verkko[a];
    // cout << "    Edustaja löytyi " << verkko[a] << "\n";
    return a;
}

bool sama(int verkko[], int a, int b)
{
    return edustaja(verkko, a) == edustaja(verkko, b);
}

void yhdista(int verkko[], int koko[], int a, int b)
{
    // a = edustaja(verkko, a);
    // b = edustaja(verkko, b);
    if (koko[a] < koko[b])
    {
        int c = a;
        a = b;
        b = c;
    }
    verkko[b] = a;
    koko[a] += koko[b];
}

int main()
{
    int n;
    cin >> n;

    vector<pair<int, pair<int, int>>> kaaret;

    int koko[n + 1];
    int verkko[n + 1];

    for (int i = 0; i < n - 1; i++)
    {
        int a, b, x;
        cin >> a >> b >> x;

        kaaret.push_back({x, {a, b}});

        koko[i + 1] = 1;
        verkko[i + 1] = i + 1;
    }
    koko[n] = 1;
    verkko[n] = n;

    sort(kaaret.rbegin(), kaaret.rend());

    long tulos = 0;

    for (auto kaari : kaaret)
    {

        int a = edustaja(verkko, kaari.second.first);
        int b = edustaja(verkko, kaari.second.second);

        // cout << "Alkusolmu " << kaari.second.first << "  loppusolmu " << kaari.second.second << "\n";
        // cout << "Lisätään " << (koko[a] * koko[b] * kaari.first) << "\n";

        tulos += (long)koko[a] * (long)koko[b] * (long)kaari.first;

        yhdista(verkko, koko, a, b);
    }

    cout << tulos << "\n";
}

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