CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko
Sender:lain
Submission time:2021-10-06 19:49:47
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.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