CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:cowperso
Submission time:2021-10-09 16:45:18
Language:C++11
Status:READY
Result:25
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.06 s2, 3details
#3--3details

Code

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

static vector<vector<pair<uint32_t, uint32_t>>> puu;
static pair<uint32_t, uint32_t> *test;

static uint64_t hitaammat(uint32_t s, uint32_t e, uint32_t vert) {
    uint64_t summa = 0;
    for (auto& seur : puu[s]) {
        if (seur.first == e) {
            if (!test)
                test = &seur;
            continue;
        }
        if (seur.second < vert)
            continue;
        summa += hitaammat(seur.first, s, vert) + 1;
    }
    return summa;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    uint64_t n;
    cin >> n;

    puu.reserve(n);

    for (uint32_t i = 0; i < n - 1; ++i) {
        uint32_t a, b, nopeus;
        cin >> a >> b >> nopeus;
        puu[a - 1].push_back({b - 1, nopeus});
        puu[b - 1].push_back({a - 1, nopeus});
    }

    uint64_t summa = 0;
    for (uint32_t i = 0; i < n; ++i) {
        for (auto& solmu : puu[i]) {
            if (i > solmu.first)
                continue;
            test = nullptr;
            summa += (hitaammat(solmu.first, i, solmu.second) + 1) * (hitaammat(i, solmu.first, solmu.second) + 1) * solmu.second;
            solmu.second -= 1;
            test->second -= 1;
        }
    }

    cout << summa << '\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:

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

correct output
1080549209850010931

user output
(empty)