oj.uz

Submission #636820

# Submission time Handle Problem Language Result Execution time Memory
636820 2022-08-30T09:38:15 Z Cross_Ratio Toll (APIO13_toll) C++14
78 / 100
 2500 ms 63760 KB 
#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
    vector<int> root;
    UnionFind(int N) {
        root.resize(N);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    bool Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if(x==y) return false;
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
        return true;
    }
};
array<long long int, 3> Edge[300005];
array<long long int, 2> Query[25];
vector<vector<int>> adj;
vector<array<long long int, 3>> rem;
int id[100005];
long long int C[100005];
long long int D[100005];
void dfs1(int c, int p, int d) {
    id[c] = d;
    D[c] = C[c];
    for(int n : adj[c]) {
        if(n==p) continue;
        dfs1(n, c, d);
        D[c] += D[n];
    }
}
long long int C2[100005];
vector<vector<int>> adj2;
long long int D2[100005];
int dep[100005];
int par[100005];
long long int E[100005];
void dfs2(int c, int p, int d) {
    par[c] = p;
    dep[c] = d;
    D2[c] = C2[c];
    for(int n : adj2[c]) {
        if(n==p) continue;
        dfs2(n, c, d+1);
        D2[c] += D2[n];
    }
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M, K;
    cin >> N >> M >> K;
    int i, j;
    for(i=0;i<M;i++) {
        cin >> Edge[i][1] >> Edge[i][2] >> Edge[i][0];
        Edge[i][1]--;
        Edge[i][2]--;
    }
    sort(Edge, Edge+M);
    UnionFind UF0(N);
    vector<array<long long int, 3>> Ed;
    for(i=0;i<M;i++) {
        if(UF0.Merge(Edge[i][1], Edge[i][2])) {
            Ed.push_back(Edge[i]);
        }
    }
    M = Ed.size();
    assert(M == N-1);
    for(i=0;i<M;i++) {
        Edge[i] = Ed[i];
    }
    for(i=0;i<K;i++) {
        cin >> Query[i][0] >> Query[i][1];
        Query[i][0]--;
        Query[i][1]--;
    }
    for(i=0;i<N;i++) cin >> C[i];
    UnionFind UF(N);
    adj.resize(N);
    for(i=0;i<K;i++) {
        UF.Merge(Query[i][0], Query[i][1]);
    }
    for(i=0;i<M;i++) {
        if(!UF.Merge(Edge[i][1], Edge[i][2])) {
            rem.push_back(Edge[i]);
        }
        else {
            adj[Edge[i][1]].push_back(Edge[i][2]);
            adj[Edge[i][2]].push_back(Edge[i][1]);
        }
    }
    for(i=0;i<N;i++) id[i] = -1;
    int cnt = 0;
    for(i=0;i<N;i++) {
        if(id[i] == -1) {
            dfs1(i, -1, cnt);
            C2[cnt] = D[i];
            cnt++;
        }
    }
    long long int ma = 0;
    set<int> S;
    S.insert(0);
    for(int m = 1; m < (1<<K); m++) {
        vector<int> V;
        int isOn = 0;
        UnionFind UF2(cnt);
        adj2.clear();
        adj2.resize(cnt);
        vector<array<int, 2>> KEdge;
        for(i=0;i<K;i++) {
            if(m & (1<<i)) {
                V.push_back(i);
                if(UF2.Merge(id[Query[i][0]], id[Query[i][1]])) {
                    int x = id[Query[i][0]];
                    int y = id[Query[i][1]];
                    adj2[x].push_back(y);
                    adj2[y].push_back(x);
                    KEdge.push_back({x, y});
                    isOn |= (1<<i);
                }
            }
        }
        if(S.find(isOn)!=S.end()) continue;
        S.insert(isOn);
        vector<array<long long int, 3>> rem2;
        for(auto it : rem) {
            if(UF2.Merge(id[it[1]], id[it[2]])) {
                int x = id[it[1]], y = id[it[2]];
                adj2[x].push_back(y);
                adj2[y].push_back(x);
            }
            else rem2.push_back(it);
        }
        dfs2(id[0], -1, 0);
        for(i=0;i<cnt;i++) E[i] = 1e18;
        for(auto it : rem2) {
            long long int cost = it[0];
            int x = id[it[1]], y = id[it[2]];
            if(dep[x] < dep[y]) swap(x, y);
            while(dep[x] > dep[y]) {
                E[x] = min(E[x], cost);
                x = par[x];
            }
            while(x != y) {
                E[x] = min(E[x], cost);
                E[y] = min(E[y], cost);
                x = par[x], y = par[y];
            }
        }
        long long int ans = 0;
        for(auto it : KEdge) {
            int x = it[0], y = it[1];
            if(par[x]==y) swap(x, y);
            ans += D2[y] * E[y];
        }
        ma = max(ma, ans);
    }
    cout << ma;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:62:12: warning: unused variable 'j' [-Wunused-variable]
   62 |     int i, j;
      |            ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 596 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 226 ms 19480 KB Output is correct
8 Correct 223 ms 19480 KB Output is correct
9 Correct 220 ms 19512 KB Output is correct

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 226 ms 19480 KB Output is correct
8 Correct 223 ms 19480 KB Output is correct
9 Correct 220 ms 19512 KB Output is correct
10 Execution timed out 2586 ms 63760 KB Time limit exceeded
11 Halted 0 ms 0 KB -