CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:tassu
Submission time:2021-10-05 17:45:05
Language:C++17
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1, 2, 3details
#2--2, 3details
#30.36 s3details

Compiler report

input/code.cpp: In function 'int find_next(const std::vector<int>&, const std::vector<int>&)':
input/code.cpp:10:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int key = 0; key < unvisited.size(); key++) {
                       ~~~~^~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int speeds_for(int, std::vector<std::vector<int> >, int)':
input/code.cpp:46:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < unvisited.size(); j++) {
                         ~~^~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int find_next(const std::vector<int>&, const std::vector<int>&)':
input/code.cpp:15:12: warning: 'smallest_key' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return smallest_key;
            ^~~~~~~~~~~~
input/code.cpp: In function 'int speeds_for(int, std::vector<std::vector<int> >, int)':
input/code.cpp:59:17: warning: 'smallest_key' may be u

Code

#include <bits/stdc++.h>
#include <vector>

using namespace std;


int find_next(const vector<int>& unvisited, const vector<int>& distances) {
    int smallest_key;
    int smallest_value = (int)INFINITY;
    for (int key = 0; key < unvisited.size(); key++) {
        if (distances[key] < smallest_value) {
            smallest_key = key;
        }
    }
    return smallest_key;
}


int speeds_for(int l, vector<vector<int>> speeds_lookup, int starting_location) {
    int total_speed = 0;

    vector<int> speeds(l);
    vector<int> distances(l);

    for (int t = 0; t < l; t++) {
        speeds[t] = (int)INFINITY;

        if (t == starting_location) {
            distances[t] = (int)INFINITY;
        } else {
            distances[t] = 0;
        }
    }

    vector<int> unvisited = vector<int>(l);
    iota(unvisited.begin(), unvisited.end(), 0);
    unvisited.erase(remove(unvisited.begin(), unvisited.end(), starting_location), unvisited.end());

    int current = starting_location;
    int current_distance, current_speed, speed_to_here, min_speed;

    for (int c = 0; c < l; c++) {
        current_distance = distances[current];
        current_speed = speeds[current];

        for (int j = 0; j < unvisited.size(); j++) {
            speed_to_here = speeds_lookup[j][current];
            if (speed_to_here == 0) {
                continue;
            }

            min_speed = min(speed_to_here, current_speed);
            speeds[j] = min_speed;
            total_speed += min_speed;

            distances[j] = current_distance + 1;
        }

        current = find_next(unvisited, distances);
        unvisited.erase(remove(unvisited.begin(), unvisited.end(), current), unvisited.end());
    }

    return total_speed;
}


int main() {
    int l;
    cin >> l;

    int a, b, x;
    vector<vector<int>> speeds(l);

    for (int i = 0; i < l; i++) {
        speeds[i] = vector<int>(l);
        for (int j = 0; j < l; j++) {
            speeds[i][j] = 0;
        }
    }

    for (int i = 1; i < l; i++) {
        cin >> a >> b >> x;
        speeds[a - 1][b - 1] = x;
        speeds[b - 1][a - 1] = x;
    }

    int speeds_total = 0;
    for (int i = 0; i < l; i++) {
        speeds_total += speeds_for(l, speeds, i);
    }
    cout << (speeds_total / 2) << "\n";

    return 0;
}

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
185949

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
(empty)

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)