Submission #25003874

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<tuple<int, int, int>> edge(N - 1);
    for (auto& [w, u, v] : edge) {
        cin >> u >> v >> w;
        u -= 1;
        v -= 1;
    }
    sort(edge.begin(), edge.end());
    atcoder::dsu dsu(N);
    long long ans = 0;
    for (const auto& [w, u, v] : edge) {
        ans += (long long) w * dsu.size(u) * dsu.size(v);
        dsu.merge(u, v);
    }
    cout << ans << '\n';
}

Submission Info

Submission Time
Task D - Sum of Maximum Weights
User KoD
Language C++ (GCC 9.2.1)
Score 400
Code Size 516 Byte
Status AC
Exec Time 79 ms
Memory 4828 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 20
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, line.txt, linelike_00.txt, linelike_01.txt, linelike_02.txt, rand_00.txt, rand_01.txt, rand_02.txt, rand_03.txt, rand_04.txt, rand_05.txt, rand_06.txt, rand_07.txt, rand_08.txt, rand_09.txt, star.txt, starlike_00.txt, starlike_01.txt, starlike_02.txt
Case Name Status Exec Time Memory
example_00.txt AC 11 ms 3636 KiB
example_01.txt AC 2 ms 3488 KiB
line.txt AC 78 ms 4636 KiB
linelike_00.txt AC 76 ms 4604 KiB
linelike_01.txt AC 79 ms 4764 KiB
linelike_02.txt AC 77 ms 4760 KiB
rand_00.txt AC 77 ms 4764 KiB
rand_01.txt AC 79 ms 4828 KiB
rand_02.txt AC 35 ms 3680 KiB
rand_03.txt AC 58 ms 4084 KiB
rand_04.txt AC 52 ms 4164 KiB
rand_05.txt AC 14 ms 3568 KiB
rand_06.txt AC 56 ms 4228 KiB
rand_07.txt AC 52 ms 3984 KiB
rand_08.txt AC 12 ms 3644 KiB
rand_09.txt AC 38 ms 3676 KiB
star.txt AC 79 ms 4656 KiB
starlike_00.txt AC 78 ms 4768 KiB
starlike_01.txt AC 77 ms 4688 KiB
starlike_02.txt AC 79 ms 4688 KiB