oj.uz

Submission #561870

# Submission time Handle Problem Language Result Execution time Memory
561870 2022-05-13T17:00:18 Z Cyanmond Toll (APIO13_toll) C++17
78 / 100
 2500 ms 19176 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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<pair<int, int>> tree[40];
    i64 nec[40];
    queue<int> que;
    int last_v[40], last_i[40];
    REP(bit, 1 << K) {
        REP(i, N) tree[i].clear();
        auto uft = uftb;
        REP(i, N) nec[i] = 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)) {
                REP(j, N) last_v[j] = last_i[j] = -1;
                last_v[E[i].a] = E[i].a;
                que.push(E[i].a);
                while (not que.empty()) {
                    const int f = que.front();
                    que.pop();
                    for (const auto &[t, c] : tree[f]) {
                        if (last_v[t] != -1) continue;
                        last_v[t] = f;
                        last_i[t] = c;
                        if (t == E[i].b) break;
                        que.push(t);
                    }
                }
                int now = E[i].b;
                while (now != E[i].a) {
                    if (last_i[now] != -1) chmin(nec[last_i[now]], E[i].cost);
                    now = last_v[now];
                } /*
 
                 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 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 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 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 2 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 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 2 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 184 ms 14016 KB Output is correct
8 Correct 226 ms 19176 KB Output is correct
9 Correct 206 ms 16628 KB Output is correct

Subtask #5
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 2 ms 212 KB Output is correct
4 Correct 2 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 184 ms 14016 KB Output is correct
8 Correct 226 ms 19176 KB Output is correct
9 Correct 206 ms 16628 KB Output is correct
10 Correct 1591 ms 14036 KB Output is correct
11 Execution timed out 2576 ms 16560 KB Time limit exceeded
12 Halted 0 ms 0 KB -