Submission #1010490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010490		vjudge1	Queue (CEOI06_queue)	C++17	0 / 100	55 ms	65536 KiB

queue

#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