oj.uz

Submission #636825

# Submission time Handle Problem Language Result Execution time Memory
636825 2022-08-30T09:41:56 Z Cross_Ratio Toll (APIO13_toll) C++14
100 / 100
 2456 ms 24392 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;
    clock_t st = clock();
    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<<K)-1; m >=0; m--) {
        if(m % 100 == 0) {
            if(clock() - st >= 2450000) break;
        }
        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)) {
                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(isOn == 0) continue;
        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) {
            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], it[0]);
                x = par[x];
            }
            while(x != y) {
                E[x] = min(E[x], it[0]);
                E[y] = min(E[y], it[0]);
                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 4 ms 468 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 4 ms 468 KB Output is correct
7 Correct 200 ms 17968 KB Output is correct
8 Correct 217 ms 18048 KB Output is correct
9 Correct 208 ms 17924 KB Output is correct

Subtask #5
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 4 ms 468 KB Output is correct
7 Correct 200 ms 17968 KB Output is correct
8 Correct 217 ms 18048 KB Output is correct
9 Correct 208 ms 17924 KB Output is correct
10 Correct 2209 ms 17980 KB Output is correct
11 Correct 2455 ms 18004 KB Output is correct
12 Correct 2456 ms 24392 KB Output is correct