oj.uz

답안 #561871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
561871 2022-05-13T17:02:29 Z Cyanmond 통행료 (APIO13_toll) C++17
78 / 100
 2500 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<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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 212 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 388 KB Output is correct
6 Correct 3 ms 340 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 388 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 203 ms 11528 KB Output is correct
8 Correct 195 ms 11376 KB Output is correct
9 Correct 181 ms 11544 KB Output is correct

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 3 ms 388 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 203 ms 11528 KB Output is correct
8 Correct 195 ms 11376 KB Output is correct
9 Correct 181 ms 11544 KB Output is correct
10 Correct 1336 ms 11520 KB Output is correct
11 Correct 2468 ms 11508 KB Output is correct
12 Execution timed out 2580 ms 11524 KB Time limit exceeded
13 Halted 0 ms 0 KB -