답안 #563520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563520 2022-05-17T11:51:14 Z KoD 통행료 (APIO13_toll) C++17
100 / 100
1655 ms 12596 KB
#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;
    }
    void clear() {
        std::fill(data.begin(), data.end(), -1);
    }
};

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];
    }
    UnionFind dsu(G);
    vector<vector<int>> graph(G);
    vector<tuple<int, int, int>> bad;
    vector<int> par(G, -1), dep(G), cost(G);
    vector<ll> sub(G);
    for (int set = 0; set < (1 << K); ++set) {
        [&] {
            dsu.clear();
            for (auto& v : graph) {
                v.clear();
            }
            for (int i = 0; i < K; ++i) {
                if (set >> i & 1) {
                    const auto& [a, b] = add[i];
                    if (!dsu.merge(a, b)) {
                        return;
                    }
                    graph[a].push_back(b);
                    graph[b].push_back(a);
                }
            }
            bad.clear();
            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);
                }
            }
            std::fill(par.begin(), par.end(), -1);
            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]);
            std::fill(cost.begin(), cost.end(), 0);
            for (int i = 0; i < K; ++i) {
                if (set >> i & 1) {
                    auto& [a, b] = add[i];
                    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 (int i = 0; i < K; ++i) {
                if (set >> i & 1) {
                    const int b = add[i].second;
                    sum += cost[b] * sub[b];
                }
            }
            ans = std::max(ans, sum);
        }();
    }
    std::cout << ans << '\n';
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 151 ms 5852 KB Output is correct
8 Correct 153 ms 6024 KB Output is correct
9 Correct 169 ms 6196 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 151 ms 5852 KB Output is correct
8 Correct 153 ms 6024 KB Output is correct
9 Correct 169 ms 6196 KB Output is correct
10 Correct 1232 ms 5888 KB Output is correct
11 Correct 1655 ms 12560 KB Output is correct
12 Correct 1643 ms 12596 KB Output is correct