oj.uz

Submission #561873

# Submission time Handle Problem Language Result Execution time Memory
561873 2022-05-13T17:05:50 Z Cyanmond Toll (APIO13_toll) C++17
100 / 100
 2381 ms 11544 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#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<char, 21> data;
    UF2() { fill(data.begin(), data.end(), -1); }
    char find(char v) {
        if (data[v] < 0)
            return v;
        else
            return data[v] = find(data[v]);
    }
    int is_same(char a, char b) { return find(a) == find(b); }
    int size(int v) { return -data[find(v)]; }
    void unite(char a, char b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (data[a] > data[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<char, char>> tree[21];
    array<int, 21> 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 << '\n';
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 194 ms 11512 KB Output is correct
8 Correct 180 ms 11456 KB Output is correct
9 Correct 176 ms 11544 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 194 ms 11512 KB Output is correct
8 Correct 180 ms 11456 KB Output is correct
9 Correct 176 ms 11544 KB Output is correct
10 Correct 1264 ms 11460 KB Output is correct
11 Correct 2237 ms 11460 KB Output is correct
12 Correct 2381 ms 11504 KB Output is correct