CSES - DatatÃ¤hti 2022 alku - Results
 Task: Tietoverkko (Network) Sender: jmarttinen Submission time: 2021-10-08 09:32:33 Language: C++11 Status: READY Result: 0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.57 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;
map<int, int> lookupTable;
map<int, set<int>> graph;

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

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

int main() {
int n, a, b, d;
long long s = 0;

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 long l, r;
// lookupTable[a]
lookupTable[network[0].second.first] = n;
for (auto edge: network) {
l = 1, r = 1;
d = edge.first;
a = edge.second.first, b = edge.second.second;
graph[a].erase(b);
graph[b].erase(a);
if (lookupTable.count(a)) {
for (auto node: graph[a])
l += search(node, a);
r = lookupTable[a] - l;
} else if (lookupTable.count(b)) {
for (auto node: graph[b])
l += search(node, b);
r = lookupTable[b] - l;
} else {
for (auto node: graph[a])
l += search(node, a);
for (auto node: graph[b])
l += search(node, b);
}

lookupTable[a] = l;
lookupTable[b] = r;
// for (auto node: graph[b]) {
//     r += search(node, b);
// }
s += l*r*d;
}
cout << s;
}```

### Test details

Group: 1, 2, 3

Verdict:

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

correct output
88687

user output
457258

#### 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
70629387810085130

#### 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)