CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:xnor
Submission time:2021-10-06 23:03:18 +0300
Language:C++17
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 <tuple>
#include <algorithm>
#include <variant>

#define ull unsigned long long int

std::vector<std::tuple<size_t, size_t, ull>> parse_args() {
    size_t n;
    std::cin >> n;

    auto edges = std::vector<std::tuple<size_t, size_t, ull>>();
    for (size_t i = 0; i < n - 1; ++i) {
        size_t a, b, speed;
        std::cin >> a >> b >> speed;
        edges.push_back(std::make_tuple(--a, --b, speed));
    }

    return edges;
}

int main() {
    auto edges = parse_args();
    auto nodes = std::vector<std::variant<ull, size_t>>(edges.size() + 1, 1ull);
    auto ns = std::vector<size_t>();
    ull total = 0;

    std::sort(edges.begin(), edges.end(), [](auto a, auto b){ return std::get<2>(a) < std::get<2>(b); });

    for (size_t i = edges.size(); i--;) {
        ns.clear();

        size_t a, b;
        ull speed;
        std::tie(a, b, speed) = edges[i];

        size_t* next;
        while ((next = std::get_if<size_t>(&nodes[a]))) {
            ns.push_back(a);
            a = *next;
        }
        while ((next = std::get_if<size_t>(&nodes[b]))) {
            ns.push_back(b);
            b = *next;
        }

        ull a_val = std::get<ull>(nodes[a]);
        ull b_val = std::get<ull>(nodes[b]);
        if (a_val < b_val) {
            std::swap(a, b);
        }

        nodes[a] = a_val + b_val;
        nodes[b] = a;

        for (size_t j = 0; j < ns.size(); ++j) {
            nodes[ns[j]] = a;
        }

        total += a_val * b_val * speed;
    }

    std::cout << total << std::endl;

    return 0;
}

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