CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:xenial
Submission time:2022-01-19 01:42:40
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s2, 3details
#3ACCEPTED0.13 s3details

Compiler report

input/code.cpp: In function 'void set_io(std::__cxx11::string)':
input/code.cpp:19: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:20: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
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>

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

struct edge {
    ll a, b, w;
};

bool cmp(edge &v1, edge &v2) {
    return v1.w > v2.w;
}

int N;
vector<edge> edges;
ll height[200005], parent[200005], Size[200005];

int find(ll n) {
    if (n != parent[n]) parent[n] = find(parent[n]);
    return parent[n];
}

void unite(ll a, ll b) {
    a = find(a),
    b = find(b);

    if (height[a] < height[b]) swap(a, b);
    if (height[a] == height[b]) height[a]++;

    parent[b] = a;
    Size[a] += Size[b];
}

int main() {
	set_io("");

    cin >> N;
    edges.rsz(N - 1);
    
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        Size[i] = 1;
    }

    for (auto &e : edges) cin >> e.a >> e.b >> e.w;
    sort(all(edges), cmp);

    ll ans = 0;
    for (auto e : edges) {
        int ra = find(e.a),
        rb = find(e.b);
        ans += Size[ra] * Size[rb] * e.w;
        unite(ra, rb);
    }

    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: 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: ACCEPTED

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

correct output
1080549209850010931

user output
1080549209850010931