Submission #1260981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260981		MisterReaper	통행료 (APIO13_toll)	C++17	0 / 100	0 ms	320 KiB

toll

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

struct DSU {
    std::vector<int> f, siz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.assign(n, 0);
        siz.assign(n, 1);
        std::iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        } 
        f[a] = b;
        siz[b] += siz[a];
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return siz[get(x)];
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M, K;
    std::cin >> N >> M >> K;

    std::vector<std::array<int, 3>> edg(M);
    for (int i = 0; i < M; ++i) {
        int A, B, C;
        std::cin >> A >> B >> C;
        --A, --B;
        edg[i] = {C, A, B};
    }

    std::sort(edg.begin(), edg.end());

    std::vector<std::array<int, 2>> mine(K);
    for (int i = 0; i < K; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        mine[i] = {A, B};
    }

    std::vector<int> P(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> P[i];
    }

    DSU dsu(N), comp(N);
    std::vector<int> ontree(N), mark(N);
    for (int i = 0; i < M; ++i) {
        auto[c, a, b] = edg[i];
        if (dsu.unite(a, b)) {
            ontree[i] = true;
        }
    }
    dsu.init(N);
    for (int i = 0; i < K; ++i) {
        mark[mine[i][0]] = true;
        mark[mine[i][1]] = true;
        comp.unite(mine[i][0], mine[i][1]);
    }

    std::vector<int> imp;
    for (int i = 0; i < M; ++i) {
        if (!ontree[i]) {
            continue;
        }
        auto[c, a, b] = edg[i];
        a = dsu.get(a), b = dsu.get(b);
        if (mark[a] && mark[b]) {
            if (comp.same(a, b)) {
                imp.emplace_back(i);
            } else {
                dsu.unite(a, b);
            }
        } else if (mark[a] || mark[b]) {
            if (mark[a]) {
                dsu.unite(b, a);
            } else {
                dsu.unite(a, b);
            }
        } else {
            dsu.unite(a, b);
        }
        comp.unite(a, b);
    }

    debug(imp);

    int n = 0;
    std::vector<int> bel(N, -1);
    std::vector<i64> p(N);
    for (int i = 0; i < N; ++i) {
        if (bel[dsu.get(i)] == -1) {
            bel[dsu.get(i)] = n++;
        }
        bel[i] = bel[dsu.get(i)];
        p[bel[i]] += P[i];
    }

    debug(bel);

    for (int i = 0; i < M; ++i) {
        auto[c, a, b] = edg[i];
        debug(c, a, b, bel[a], bel[b]);
        edg[i] = {c, bel[a], bel[b]};
    }
    for (int i = 0; i < K; ++i) {
        auto[a, b] = mine[i];
        mine[i] = {bel[a], bel[b]};
    }

    std::vector<int> dep(n), par(n), val(n);
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    auto dfs1 = [&](auto&& self, int v) -> void {
        for (auto[u, w] : adj[v]) {
            if (u == par[v]) {
                continue;
            }
            dep[u] = dep[v] + 1;
            par[u] = v;
            val[u] = int(1E9);
            self(self, u);
        }
    };

    auto minim = [&](int a, int b, int x) -> void {
        if (dep[a] < dep[b]) {
            std::swap(a, b);
        }
        while (dep[a] != dep[b]) {
            val[a] = std::min(val[a], x);
            a = par[a];
        }
        while (a != b) {
            val[a] = std::min(val[a], x);
            val[b] = std::min(val[b], x);
            a = par[a];
            b = par[b];
        }
    };

    i64 res = 0;
    auto dfs2 = [&](auto&& self, int v) -> void {
        for (auto[u, w] : adj[v]) {
            if (u == par[v]) {
                continue;
            }
            self(self, u);
            if (w) {
                res += p[u] * val[u];
            }
            p[v] += p[u];
        }
    };

    i64 ans = 0;
    for (int m = 1; m < (1 << K); ++m) {
        dsu.init(n);
        adj.assign(n, {});
        bool bad = false;
        for (int i = 0; i < K; ++i) {
            if (~m >> i & 1) {
                continue;
            }
            if (!dsu.unite(mine[i][0], mine[i][1])) {
                bad = true;
                break;
            }
            debug(mine[i][0], mine[i][1]);
            adj[mine[i][0]].emplace_back(mine[i][1], 1);
            adj[mine[i][1]].emplace_back(mine[i][0], 1);
        }

        if (bad) {
            continue;
        }

        debug(m);

        std::vector<int> minimp;
        for (auto i : imp) {
            debug(edg[i][1], edg[i][2]);
            if (dsu.unite(edg[i][1], edg[i][2])) {
                adj[edg[i][1]].emplace_back(edg[i][2], 0);
                adj[edg[i][2]].emplace_back(edg[i][1], 0);
            } else {
                minimp.emplace_back(i);
            }
        }

        debug("great");

        assert(dsu.size(0) == n);

        dfs1(dfs1, 0);

        for (auto i : minimp) {
            minim(edg[i][1], edg[i][2], edg[i][0]);
        }

        res = 0;
        dfs2(dfs2, 0);

        ans = std::max(ans, res);
    }

    std::cout << ans << '\n';

    return 0;
}

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