CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:lain
Submission time:2021-10-06 19:49:47 +0300
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s2, 3details
#3ACCEPTED0.10 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d\n", &n);
   ~~~~~^~~~~~~~~~~~
input/code.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d\n", &a, &b, &weight);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
struct Edge {
int a, b, w;
};
constexpr int N = 2 * 1e5 + 100;
typedef long long ll;
ll sz[N];
ll parent[N];
vector<Edge> tree;
int find_set(int i) {
return i == parent[i] ? i : parent[i] = find_set(parent[i]);
}
void union_set(int a_, int b_) {
int a = find_set(a_);
int b = find_set(b_);
if (a != b) {
if (sz[a] < sz[b])
swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
scanf("%d\n", &n);
for (int i = 0; i < n - 1; ++i) {
int a, b, weight;
scanf("%d %d %d\n", &a, &b, &weight);
Edge edge{
.a = a,
.b = b,
.w = weight,
};
tree.push_back(edge);
}
sort(all(tree), [](const auto &a, const auto &b) { return a.w < b.w; });
for (ll i = 0; i < N; i++)
parent[i] = i, sz[i] = 1;
ll result = 0;
for (ll i = tree.size() - 1; i >= 0; --i) {
int a = tree[i].a;
int b = tree[i].b;
result += tree[i].w * ((ll)sz[find_set(a)] * (ll)sz[find_set(b)]);
union_set(a, b);
}
printf("%lld\n", result);
return 0;
}

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