CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:jmarttinen
Submission time:2021-10-06 11:17:25 +0300
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.59 s2, 3details
#3--3details

Code

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

vector<pair<int, pair<int,int>>> network;

long search(int node, map<int,set<int>>& graph, int ignoredNode) {
    if (graph[node].size() <= 1) {
        return 1;
    }
    long s = 0;

    for (auto n : graph[node]) {
        if (n == ignoredNode) {
            continue;
        }
        s += search(n, graph, node);

    }

    return s;
}

int main() {
    int n, a, b, d;
    long s = 0;
    map<int, set<int>> graph;

    cin >> n;
    for (int i=1; i<n; i++) {
        graph[i] = set<int>();
    }
    for (int i=0; i<n-1; i++) {
        cin >> a >> b >> d;
        graph[a].insert(b);
        graph[b].insert(a);
        network.push_back(pair<int, pair<int,int>>(d, pair<int,int>(a,b)));
    }
    sort(network.begin(), network.end());

    long l, r;
    for (auto node: network) {
        l = 1, r = 1;
        d = node.first;
        a = node.second.first, b = node.second.second;
        graph[a].erase(b);
        graph[b].erase(a);
        for (auto n: graph[a]) {
            l += search(n, graph, a);
        }
        for (auto n: graph[b]) {
            r += search(n, graph, b);
        }
        // graph[a].insert(b);
        // graph[b].insert(a);
        s += l*r*d;
    }
    cout << s;
}

Test details

Test 1

Group: 1, 2, 3

Verdict:

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

correct output
88687

user output
35612

Test 2

Group: 2, 3

Verdict:

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

correct output
1103702320243776

user output
353509489536021

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)