Submission #563517

#	Time	Username	Problem	Language	Result	Execution time	Memory
563517		KoD	Toll (APIO13_toll)	C++17	78 / 100	2517 ms	12712 KiB

toll

#include <bits/stdc++.h>

using ll = long long;

using std::vector;
using std::array;
using std::pair;
using std::tuple;

struct UnionFind {
    vector<int> data;
    UnionFind(const int n) : data(n, -1) {}
    int find(const int u) {
        return data[u] < 0 ? u : data[u] = find(data[u]);
    }
    bool merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) {
            return false;
        }
        if (data[u] > data[v]) {
            std::swap(u, v);
        }
        data[u] += data[v];
        data[v] = u;
        return true;
    }
    vector<vector<int>> groups() {
        const int n = data.size();
        vector<vector<int>> ret(n);
        for (int i = 0; i < n; ++i) {
            ret[find(i)].push_back(i);
        }
        const auto itr = std::remove_if(ret.begin(), ret.end(), [&](const std::vector<int>& v) { return v.empty(); });
        ret.erase(itr, ret.end());
        return ret;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M, K;
    std::cin >> N >> M >> K;
    const auto edges = [&] {
        vector<tuple<int, int, int>> all(M);
        for (auto& [c, a, b] : all) {
            std::cin >> a >> b >> c;
            a -= 1, b -= 1;
        }
        std::sort(all.begin(), all.end());
        vector<tuple<int, int, int>> ret;
        ret.reserve(N - 1);
        UnionFind dsu(N);
        for (const auto& [c, a, b] : all) {
            if (dsu.merge(a, b)) {
                ret.emplace_back(a, b, c);
            }
        }
        return ret;
    }();
    vector<pair<int, int>> add(K);
    UnionFind add_only(N);
    for (auto& [a, b] : add) {
        std::cin >> a >> b;
        a -= 1, b -= 1;
        add_only.merge(a, b);
    }
    vector<int> pop(N);
    for (auto& x : pop) {
        std::cin >> x;
    }
    ll ans = 0;
    UnionFind compress(N);
    vector<tuple<int, int, int>> important;
    for (const auto& [a, b, c] : edges) {
        if (add_only.merge(a, b)) {
            compress.merge(a, b);
        } else {
            important.emplace_back(a, b, c);
        }
    }
    const auto groups = compress.groups();
    const int G = groups.size();
    vector<int> id(N);
    vector<ll> pop_sum(G);
    for (int i = 0; i < G; ++i) {
        for (const int u : groups[i]) {
            id[u] = i;
            pop_sum[i] += pop[u];
        }
    }
    for (auto& [a, b] : add) {
        a = id[a], b = id[b];
    }
    for (auto& [a, b, c] : important) {
        a = id[a], b = id[b];
    }
    for (int set = 0; set < (1 << K); ++set) {
        [&] {
            vector<pair<int, int>> use;
            for (int i = 0; i < K; ++i) {
                if (set >> i & 1) {
                    use.push_back(add[i]);
                }
            }
            UnionFind dsu(G);
            vector<vector<int>> graph(G);
            for (const auto& [a, b] : use) {
                if (!dsu.merge(a, b)) {
                    return;
                }
                graph[a].push_back(b);
                graph[b].push_back(a);
            }
            vector<tuple<int, int, int>> bad;
            for (const auto& [a, b, c] : important) {
                if (dsu.merge(a, b)) {
                    graph[a].push_back(b);
                    graph[b].push_back(a);
                } else {
                    bad.emplace_back(a, b, c);
                }
            }
            vector<int> par(G, -1), dep(G);
            vector<ll> sub(G);
            auto setup = [&](auto&& self, const int u) -> void {
                sub[u] = pop_sum[u];
                for (const int v : graph[u]) {
                    if (v != par[u]) {
                        par[v] = u;
                        dep[v] = dep[u] + 1;
                        self(self, v);
                        sub[u] += sub[v];
                    }
                }
            };
            setup(setup, id[0]);
            vector<int> cost(G);
            for (auto& [a, b] : use) {
                if (dep[a] > dep[b]) {
                    std::swap(a, b);
                }
                cost[b] = 1000000;
            }
            for (auto [a, b, c] : bad) {
                while (a != b) {
                    if (dep[a] > dep[b]) {
                        cost[a] = std::min(cost[a], c);
                        a = par[a];
                    } else {
                        cost[b] = std::min(cost[b], c);
                        b = par[b];
                    }
                } 
            }
            ll sum = 0;
            for (const auto& [a, b] : use) {
                sum += cost[b] * sub[b];
            }
            ans = std::max(ans, sum);
        }();
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 0 / 22