oj.uz

Submission #561869

# Submission time Handle Problem Language Result Execution time Memory
561869 2022-05-13T16:56:25 Z Cyanmond Toll (APIO13_toll) C++17
78 / 100
 2500 ms 19180 KB 
#include <bits/stdc++.h>
 
using namespace std;
using i64 = int64_t;
 
constexpr i64 inf = 1ll << 60;
 
#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 Merger {
    int n;
    vector<int> roots;
    vector<vector<int>> vals;
    Merger(const int n_) {
        n = n_;
        roots.assign(n, -1);
        REP(i, n) vals.push_back({i});
    }
    int find(int a) {
        if (roots[a] < 0)
            return a;
        else
            return roots[a] = find(roots[a]);
    }
    int size(int v) { return -roots[find(v)]; }
    void merge(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size(a) < size(b)) swap(a, b);
        for (const int e : vals[b]) vals[a].push_back(e);
        roots[a] += roots[b];
        roots[b] = a;
    }
};
 
struct Edge {
    i64 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);
        REP(i, K) uft.unite(A[i].first, A[i].second);
        Merger mt(N);
        for (const auto &[cost, a, b] : E) {
            if (uft.is_same(a, b)) continue;
            uft.unite(a, b);
            mt.merge(a, b);
        }
 
        vector<bool> used(N);
        vector<vector<int>> groups;
        REP(i, N) {
            if (used[mt.find(i)]) continue;
            used[mt.find(i)] = true;
            groups.push_back(mt.vals[mt.find(i)]);
        }
        const int L = (int)size(groups);
 
        for (auto &g : groups) sort(g.begin(), g.end());
        sort(groups.begin(), groups.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        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;
        for (const auto &[cost, a, b] : E)
            if (a != b) E2.push_back({cost, a, b});
        E = E2;
        E2.clear();
 
        uft = UnionFind(L);
        for (const auto &[cost, a, b] : E) {
            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;
    UnionFind uftb(N);
    vector<vector<pair<int, int>>> tree(N);
    vector<i64> nec(N);
    REP(bit, 1 << K) {
        REP(i, N) tree[i].clear();
        auto uft = uftb;
        fill(nec.begin(),nec.end(),inf);
        bool possible = true;
        REP(i, K) {
            if (bit & (1 << i)) {
                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 (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;
                };
                assert(dfs(dfs, E[i].a, -1));
            } else {
                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 244 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 244 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 1 ms 244 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 3 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 244 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 3 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 185 ms 14156 KB Output is correct
8 Correct 193 ms 19180 KB Output is correct
9 Correct 188 ms 16620 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 244 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 3 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 185 ms 14156 KB Output is correct
8 Correct 193 ms 19180 KB Output is correct
9 Correct 188 ms 16620 KB Output is correct
10 Correct 1435 ms 14044 KB Output is correct
11 Correct 2463 ms 16564 KB Output is correct
12 Execution timed out 2578 ms 16560 KB Time limit exceeded
13 Halted 0 ms 0 KB -