Submission #636825

#	Time	Username	Problem	Language	Result	Execution time	Memory
636825		Cross_Ratio	Toll (APIO13_toll)	C++14	100 / 100	2456 ms	24392 KiB

toll

#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 (stderr)

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

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22