oj.uz

Submission #561863

# Submission time Handle Problem Language Result Execution time Memory
561863 2022-05-13T16:50:01 Z Cyanmond Toll (APIO13_toll) C++17
78 / 100
 2500 ms 17912 KB 
#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr int inf = 1 << 30;

#define REP(i, n) for (int i = 0; i < (n); ++i)

template <typename T> void chmax(T &a, const T b) {
    if (a < b) a = b;
}

template <typename T> void chmin(T &a, const T b) {
    if (a > b) a = b;
}

struct UnionFind {
    int n;
    vector<int> data;
    UnionFind(const int n_) : n(n_), data(n, -1) {}
    int find(int v) {
        if (data[v] < 0)
            return v;
        else
            return data[v] = find(data[v]);
    }
    int is_same(int a, int b) { return find(a) == find(b); }
    int size(int v) { return -data[find(v)]; }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size(a) < size(b)) swap(a, b);
        data[a] += data[b];
        data[b] = a;
    }
};

struct UF2 {
    array<int, 22> data;
    UF2() { fill(data.begin(), data.end(), -1); }
    int find(int v) {
        if (data[v] < 0)
            return v;
        else
            return data[v] = find(data[v]);
    }
    int is_same(int a, int b) { return find(a) == find(b); }
    int size(int v) { return -data[find(v)]; }
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size(a) < size(b)) swap(a, b);
        data[a] += data[b];
        data[b] = a;
    }
};

struct Edge {
    int cost;
    int a;
    int b;
};

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

    int N, M, K;
    cin >> N >> M >> K;
    vector<Edge> E(M);
    REP(i, M) {
        cin >> E[i].a >> E[i].b >> E[i].cost;
        --E[i].a, --E[i].b;
    }
    vector<pair<int, int>> A(K);
    for (auto &[x, y] : A) {
        cin >> x >> y;
        --x, --y;
    }
    vector<i64> P(N);
    for (auto &e : P) cin >> e;
    sort(E.begin(), E.end(), [](Edge &a, Edge &b) { return a.cost < b.cost; });

    {
        UnionFind uft(N);
        int L = 1;
        REP(i, K) {
            if (uft.is_same(A[i].first, A[i].second)) --L;
            ++L;
            uft.unite(A[i].first, A[i].second);
        }
        vector<vector<int>> graph(N);
        for (const auto &[cost, a, b] : E) {
            if (uft.is_same(a, b)) continue;
            uft.unite(a, b);
            graph[a].push_back(b);
            graph[b].push_back(a);
        }

        vector<char> used(N);
        vector<vector<int>> groups(L);
        int cnt = 0;
        REP(i, N) {
            if (used[i]) continue;
            auto dfs = [&](auto &&self, const int v) -> void {
                used[v] = true;
                groups[cnt].push_back(v);
                for (const int t : graph[v]) {
                    if (used[t]) continue;
                    self(self, t);
                }
            };
            dfs(dfs, i);
            ++cnt;
        }
        vector<int> att(N);
        REP(i, L) {
            const auto &g = groups[i];
            for (const int e : g) att[e] = i;
        }
        vector<i64> NP(L);
        REP(i, N) NP[att[i]] += P[i];
        P = move(NP);
        for (auto &[x, y] : A) {
            x = att[x];
            y = att[y];
        }
        REP(i, M) {
            E[i].a = att[E[i].a];
            E[i].b = att[E[i].b];
        }

        vector<Edge> E2;
        uft = UnionFind(L);
        for (const auto &[cost, a, b] : E) {
            if (a == b) continue;
            if (uft.is_same(a, b)) continue;
            uft.unite(a, b);
            E2.push_back({cost, a, b});
        }
        E = move(E2);
        N = L;
        M = (int)size(E);
    }

    i64 ans = 0;
    UF2 uft;
    vector<pair<int, int>> tree[22];
    array<int, 22> nec;
    REP(bit, 1 << K) {
        REP(i, N) tree[i].clear();
        fill(uft.data.begin(), uft.data.end(), -1);
        fill(nec.begin(), nec.end(), inf);
        bool possible = true;
        int cnt = 0;
        REP(i, K) {
            if (bit & (1 << i)) {
                ++cnt;
                if (uft.is_same(A[i].first, A[i].second)) {
                    possible = false;
                    break;
                }
                uft.unite(A[i].first, A[i].second);
                tree[A[i].first].emplace_back(A[i].second, i);
                tree[A[i].second].emplace_back(A[i].first, i);
            }
        }
        if (not possible) continue;
        REP(i, M) {
            if (cnt == N - 1 or uft.is_same(E[i].a, E[i].b)) {
                auto dfs = [&](auto &&self, const int v, const int p) -> bool {
                    for (auto &[t, c] : tree[v]) {
                        if (t == p) continue;
                        if (t == E[i].b) {
                            chmin(nec[c], E[i].cost);
                            return true;
                        }
                        if (self(self, t, v)) {
                            chmin(nec[c], E[i].cost);
                            return true;
                        }
                    }
                    return false;
                };
                dfs(dfs, E[i].a, -1);
            } else {
                ++cnt;
                uft.unite(E[i].a, E[i].b);
                tree[E[i].a].emplace_back(E[i].b, -1);
                tree[E[i].b].emplace_back(E[i].a, -1);
            }
        }

        i64 res = 0;
        auto dfs = [&](auto &&self, const int v, const int p) -> i64 {
            i64 sum = 0;
            for (const auto &[t, c] : tree[v]) {
                if (t == p) continue;
                const i64 e = self(self, t, v);
                if (c != -1) res += nec[c] * e;
                sum += e;
            }
            return sum + P[v];
        };
        dfs(dfs, 0, -1);
        chmax(ans, res);
    }

    cout << ans << endl;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 460 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 191 ms 11524 KB Output is correct
8 Correct 185 ms 11400 KB Output is correct
9 Correct 181 ms 11544 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 191 ms 11524 KB Output is correct
8 Correct 185 ms 11400 KB Output is correct
9 Correct 181 ms 11544 KB Output is correct
10 Correct 1369 ms 11500 KB Output is correct
11 Correct 2346 ms 11388 KB Output is correct
12 Execution timed out 2552 ms 17912 KB Time limit exceeded
13 Halted 0 ms 0 KB -