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

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);
    }
}

const int MX = 200001;

vector<pair<int, pair<int, int>>> edges;
int parent[MX], Size[MX];

bool cmp(pair<int, pair<int, int>> v1, pair<int, pair<int, int>> v2) {
    return v1.fi > v2.fi;
}

int Find(int n) {
    while (parent[n] != n) n = parent[n];
    return n;
}

void unite(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (Size[a] < Size[b]) swap(a, b);
    Size[a] += Size[b];
    parent[b] = a;
}

int main() {
    set_io();

    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b, x; cin >> a >> b >> x;
        edges.pb({x, {a-1, b-1}});
    }
    sort(all(edges), cmp);

    for (int i = 0; i < n; i++) {
        parent[i] = i;
        Size[i] = 1;
    }

    ll ans = 0;
    for (auto edge : edges) {
        int a = Find(edge.se.fi), b = Find(edge.se.se);
        ans += edge.fi * (Size[a] * Size[b]);
        unite(a, b);
    }
    cout << ans;
}

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
1794100716608

Test 3

Group: 3

Verdict:

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

correct output
1080549209850010931

user output
71708898778419