CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:ToukoP
Submission time:2021-10-06 18:04:27
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#20.01 s2, 3details
#30.42 s3details

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;
            long cache = con->destCount;

            bool flip = current == dest;
            if (flip) {
                dest = con->origin;
                cache = con->originCount;
            }

            if (origin == dest) {
                continue;
            }

            if (cache != -1) {
                sum += cache;
                continue;
            }

            long count = calcSize(current, dest, nodes);
            if (flip) {
                con->originCount = count;
            } else {
                con->destCount = count;
            }
            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:

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

correct output
88687

user output
483346

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
19004829002336058

Test 3

Group: 3

Verdict:

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

correct output
1080549209850010931

user output
5440813742279624201