Task: | Tietoverkko |
Sender: | lain |
Submission time: | 2021-10-06 19:49:47 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | ACCEPTED | 15 |
#3 | ACCEPTED | 75 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 2, 3 | details |
#3 | ACCEPTED | 0.10 s | 3 | details |
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 |