oj.uz

Submission #563465

# Submission time Handle Problem Language Result Execution time Memory
563465 2022-05-17T09:29:50 Z KoD Toll (APIO13_toll) C++17
56 / 100
 2500 ms 16252 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;
    }
};

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);
    for (auto& [a, b] : add) {
        std::cin >> a >> b;
        a -= 1, b -= 1;
    }
    vector<int> pop(N);
    for (auto& x : pop) {
        std::cin >> x;
    }
    ll ans = 0;
    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(N);
            vector<vector<int>> graph(N);
            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] : edges) {
                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(N), dep(N);
            vector<ll> sub(N);
            auto setup = [&](auto&& self, const int u) -> void {
                sub[u] = pop[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, 0);
            vector<int> cost(N);
            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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 4 ms 316 KB Output is correct
4 Correct 4 ms 232 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 4 ms 316 KB Output is correct
4 Correct 4 ms 232 KB Output is correct
5 Correct 143 ms 476 KB Output is correct
6 Correct 78 ms 468 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 4 ms 316 KB Output is correct
4 Correct 4 ms 232 KB Output is correct
5 Correct 143 ms 476 KB Output is correct
6 Correct 78 ms 468 KB Output is correct
7 Execution timed out 2535 ms 16252 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 4 ms 316 KB Output is correct
4 Correct 4 ms 232 KB Output is correct
5 Correct 143 ms 476 KB Output is correct
6 Correct 78 ms 468 KB Output is correct
7 Execution timed out 2535 ms 16252 KB Time limit exceeded
8 Halted 0 ms 0 KB -