oj.uz

Submission #1010490

# Submission time Handle Problem Language Result Execution time Memory
1010490 2024-06-29T07:14:18 Z vjudge1 Queue (CEOI06_queue) C++17
0 / 100
 55 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

struct dsu {
    vector<int> par, size;

    dsu(int n) {
        par.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i++) par[i] = i;
    }

    int find(int v) {
        return par[v] == v ? v : par[v] = find(par[v]);
    }

    void merge(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) {
            if (size[a] < size[b]) swap(a, b);
            par[b] = a;
            size[a] += size[b];
        }
    }

    long long findsize(int v) {
        return size[find(v)];
    }
};

struct edge {
    int u,v,w;

    friend bool operator< (edge a, edge b) {
        return a.w == b.w ? a.u < b.u : a.w < b.w;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t; cin >> t; while (t--) {
        int n; cin >> n;
        edge tree[n-1];
        dsu d = dsu(n);
        for (auto& [u, v, w] : tree) {
            cin >> u >> v >> w;
            u--, v--;
        }
        sort(tree, tree + n-1);

        long long ans = 0;
        for (auto [u, v, w] : tree) {
            ans += w;
            ans += (d.findsize(u) * d.findsize(v) - 1) * (w + 1);
            d.merge(u, v);
        }
        cout << ans << "\n";
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Runtime error 1 ms 604 KB Execution killed with signal 11
3 Runtime error 1 ms 604 KB Execution killed with signal 6
4 Runtime error 38 ms 65536 KB Execution killed with signal 9
5 Runtime error 55 ms 65536 KB Execution killed with signal 9
6 Runtime error 47 ms 65536 KB Execution killed with signal 9
7 Runtime error 40 ms 65536 KB Execution killed with signal 9
8 Runtime error 40 ms 65536 KB Execution killed with signal 9
9 Runtime error 40 ms 65536 KB Execution killed with signal 9
10 Runtime error 46 ms 65536 KB Execution killed with signal 9
11 Runtime error 40 ms 65536 KB Execution killed with signal 9
12 Runtime error 9 ms 2648 KB Execution killed with signal 11
13 Runtime error 37 ms 65536 KB Execution killed with signal 9
14 Runtime error 52 ms 65536 KB Execution killed with signal 9
15 Runtime error 47 ms 65536 KB Execution killed with signal 9
16 Runtime error 36 ms 65536 KB Execution killed with signal 9
17 Runtime error 39 ms 65536 KB Execution killed with signal 9
18 Runtime error 40 ms 65536 KB Execution killed with signal 9
19 Runtime error 37 ms 65536 KB Execution killed with signal 9
20 Runtime error 37 ms 65536 KB Execution killed with signal 9
21 Runtime error 40 ms 65536 KB Execution killed with signal 9
22 Runtime error 37 ms 65536 KB Execution killed with signal 9
23 Runtime error 40 ms 65536 KB Execution killed with signal 9
24 Runtime error 39 ms 65536 KB Execution killed with signal 9
25 Runtime error 41 ms 65536 KB Execution killed with signal 9