CSES - DatatÃ¤hti 2022 alku - Results
 Task: Tietoverkko Sender: ToukoP Submission time: 2021-10-06 18:07:33 Language: C++11 Status: READY Result: 25
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.09 s2, 3details
#3--3details

Code

```#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

struct Connection {
long destination, speed, origin;
long originCount = -1, destCount = -1;
bool disabled = false;

Connection(long speed, long dest, long origin) {
this->destination = dest;
this->speed = speed;
this->origin = origin;
}
};

long calcSize(long origin, long current, vector<Connection*> nodes[]) {
long sum = 1;

for (long i = 0; (unsigned) i < nodes[current].size(); i++) {
Connection* con = nodes[current].at(i);
if (!con->disabled) {
long dest = con->destination;

if (current == dest) {
dest = con->origin;
}

if (origin == dest) {
continue;
}

long count = calcSize(current, dest, nodes);
sum += count;
}
}

return sum;
}

bool compareConnections(Connection* c1, Connection* c2) {
return c1->speed < c2->speed;
}

long solve(vector<Connection*> nodes[], vector<Connection*> connections) {

sort(connections.begin(), connections.end(), compareConnections);

long res = 0;
for (long i = 0; (unsigned) i < connections.size(); i++) {
Connection* con = connections.at(i);
long a = calcSize(con->origin, con->destination, nodes);
long b = calcSize(con->destination, con->origin, nodes);
con->disabled = true;
res += a * b * con->speed;
}
return res;
}

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

vector<Connection*> nodes [n + 1];
vector<Connection*> connections;

for (long i = 0; i < n - 1; i++) {
long a, b, x;
cin >> a >> b >> x;
Connection* con = new Connection(x, a, b);
nodes[a].push_back(con);
nodes[b].push_back(con);
connections.push_back(con);
}

long output = solve(nodes, connections);

cout << output;
}```

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)