oj.uz

답안 #625272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
625272 2022-08-09T18:13:41 Z MohamedFaresNebili 통행료 (APIO13_toll) C++14
100 / 100
 1697 ms 28368 KB 
#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound
            #define int ll

            const int MOD = 998244353;

            int N, M, K, P[100005], par[100005];
            int calc[100005], dep[100005], anc[100005], nat[100005];
            int Key[100005], val[100005];
            vector<int> A, B, C, X, Y;
            vector<int> adj[100005];
            vector<pair<int, int>> G[100005];

            bool compare(int u, int v) {
                return C[u] < C[v];
            }
            int findSet(int v) {
                if(par[v] == v) return v;
                return par[v] = findSet(par[v]);
            }
            bool unionSet(int u, int v) {
                u = findSet(u), v = findSet(v);
                if(u == v) return 0;
                par[u] = v; return 1;
            }
            void dfs(int v, int id) {
                Key[v] = id; val[id] += P[v];
                for(auto u : adj[v]) {
                    if(Key[u] == -1) dfs(u, id);
                }
            }
            void DFS(int v, int p) {
                calc[v] = val[v]; dep[v] = dep[p] + 1;
                anc[v] = p;
                for(auto u : G[v]) {
                    if(u.first == p) continue;
                    nat[u.first] = u.second;
                    DFS(u.first, v); calc[v] += calc[u.first];
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M >> K;
                A.resize(M), B.resize(M), C.resize(M);
                for(int l = 0; l < M; l++) {
                    cin >> A[l] >> B[l] >> C[l];
                    --A[l], --B[l];
                }
                X.resize(K), Y.resize(K);
                for(int l = 0; l < K; l++) {
                    cin >> X[l] >> Y[l];
                    --X[l], --Y[l];
                }
                for(int l = 0; l < N; l++) cin >> P[l];
                vector<int> edges(M);
                iota(edges.begin(), edges.end(), 0);
                sort(edges.begin(), edges.end(), compare);
                for(int l = 0; l < N; l++) par[l] = l;
                vector<int> _A, _B, _C;
                for(auto u : edges) {
                    if(unionSet(A[u], B[u])) {
                        _A.push_back(A[u]);
                        _B.push_back(B[u]);
                        _C.push_back(C[u]);
                    }
                }
                swap(A, _A), swap(B, _B), swap(C, _C);
                M = A.size();
                for(int l = 0; l < N; l++) par[l] = l;
                for(int l = 0; l < K; l++) {
                    unionSet(X[l], Y[l]);
                }
                vector<array<int, 3>> E;
                for(int l = 0; l < M; l++) {
                    if(unionSet(A[l], B[l])) {
                        adj[A[l]].push_back(B[l]);
                        adj[B[l]].push_back(A[l]);
                    }
                    else E.push_back({A[l], B[l], C[l]});
                }
                int cur = 0; memset(Key, -1, sizeof Key);
                for(int l = 0; l < N; l++) {
                    if(Key[l] == -1) {
                        dfs(l, cur); ++cur;
                    }
                }
                for(int l = 0; l < K; l++) {
                    X[l] = Key[X[l]];
                    Y[l] = Key[Y[l]];
                }
                for(auto& u : E) {
                    u[0] = Key[u[0]];
                    u[1] = Key[u[1]];
                }
                int res = 0;
                for(int l = 1; l < (1 << K); l++) {

                    for(int i = 0; i < cur; i++)
                        par[i] = i;
                    bool ok = 1;
                    for(int i = 0; i < K; i++) {
                        if(l & (1 << i))
                            ok &= unionSet(X[i], Y[i]);
                    }
                    if(!ok) continue;
                    for(int i = 0; i < cur; i++) G[i].clear();
                    for(int i = 0; i < K; i++) {
                        if(l & (1 << i)) {
                            G[X[i]].push_back({Y[i], 1});
                            G[Y[i]].push_back({X[i], 1});
                        }
                    }
                    vector<array<int, 3>> Q;
                    for(auto u : E) {
                        if(!unionSet(u[0], u[1]))
                            Q.push_back(u);
                        else {
                            G[u[0]].push_back({u[1], 0});
                            G[u[1]].push_back({u[0], 0});
                        }
                    }
                    DFS(0, 0); vector<int> arr(cur, 1e9);
                    for(auto q : Q) {
                        int u = q[0], v = q[1], w = q[2];
                        if(dep[u] < dep[v]) swap(u, v);
                        while(dep[u] > dep[v]) {
                            arr[u] = min(arr[u], w);
                            u = anc[u];
                        }
                        while(u != v) {
                            arr[u] = min(arr[u], w);
                            arr[v] = min(arr[v], w);
                            u = anc[u]; v = anc[v];
                        }
                    }
                    int ans = 0;
                    for(int i = 0; i < cur; i++) {
                        ans += calc[i] * arr[i] * nat[i];
                    }
                    res = max(res, ans);
                }
                cout << res << "\n";
                return 0;
            }

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5792 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5792 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 5 ms 6120 KB Output is correct
6 Correct 5 ms 6100 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5792 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 5 ms 6120 KB Output is correct
6 Correct 5 ms 6100 KB Output is correct
7 Correct 226 ms 28368 KB Output is correct
8 Correct 247 ms 25972 KB Output is correct
9 Correct 245 ms 26180 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5844 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5792 KB Output is correct
4 Correct 4 ms 5844 KB Output is correct
5 Correct 5 ms 6120 KB Output is correct
6 Correct 5 ms 6100 KB Output is correct
7 Correct 226 ms 28368 KB Output is correct
8 Correct 247 ms 25972 KB Output is correct
9 Correct 245 ms 26180 KB Output is correct
10 Correct 1325 ms 26008 KB Output is correct
11 Correct 1697 ms 26060 KB Output is correct
12 Correct 1672 ms 26076 KB Output is correct