CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:xenial
Submission time:2021-10-05 20:39:35
Language:C++17
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2--2, 3details
#3--3details

Compiler report

input/code.cpp: In function 'void set_io(std::__cxx11::string)':
input/code.cpp:16:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen((filename + ".in").c_str(), "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen((filename + ".out").c_str(), "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define sz size
#define rsz resize

void set_io(string filename = "") {
    ios::sync_with_stdio(0);
	cin.tie(0);

    if (filename != "") {
        freopen((filename + ".in").c_str(), "r", stdin);
        freopen((filename + ".out").c_str(), "w", stdout);
    }
}

vector<vector<pair<int,int>>> adj;
vector<bool> visited;

int dfs(int a, int b, int bs) {
    visited[a] = true;
    int ans = INT_MAX;
    for (auto n : adj[a]) {
        if (visited[n.fi]) continue;
        if (n.fi == b) return min(n.se, bs);
        int temp = dfs(n.fi, b, min(n.se, bs));
        ans = min(ans, temp);
    }

    return ans;
}

int main() {
    set_io("");

    int n; cin >> n;
    adj.rsz(n);
    for (int i = 0; i < n-1; i++) {
        int a, b, x; cin >> a >> b >> x;
        adj[a-1].pb({b-1, x});
        adj[b-1].pb({a-1, x});
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            visited = vector<bool>(n, false);
            ans += dfs(i, j, INT_MAX);
        }
    }
    cout << ans << endl;
}

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:

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)