Submission #233822

#	Time	Username	Problem	Language	Result	Execution time	Memory
233822		crackersamdjam	Toll (APIO13_toll)	C++14	16 / 100	174 ms	163844 KiB

toll

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
constexpr int MM = 1e5+1;

ll compsz[MM], ans;
int n, m, k, par[MM], compid[MM], sz[MM];
vector<int> adj[MM];

int find(int x){
    while(x != par[x])
        x = par[x], par[x] = par[par[x]];
    return x;
}

void reset(){
    for(int i = 0; i <= n; i++)
        par[i] = i;
}

int mp(int i){
    return compid[i];
}

struct edge{
    int a, b, c;
    bool operator<(const edge o) const{
        return c < o.c;
    }
};
vector<edge> edges, toll, use, maybe, no;
int pre[MM], dep[MM], dp[MM];

void dfs(int cur){
    for(int u: adj[cur]){
        if(u != pre[cur]){
            pre[u] = cur;
            dep[u] = dep[cur]+1;
            dfs(u);
            compsz[cur] += compsz[u]; //subtree sz
        }
    }
}

void go(int mask){
    for(int i = 0; i < 25; i++){
        par[i] = i;
        dp[i] = 1e6;
    }
    
    for(int i = 0; i < k; i++){
        if(mask&(1<<i)){
            int a = find(mp(toll[i].a)), b = find(mp(toll[i].b));
            if(a == b)
                return; //cycle
            par[a] = b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
    }
    
    //add so that graph is connected
    no.clear();
    for(auto e: maybe){
        int a = find(e.a), b = find(e.b);
        if(a != b)
            par[a] = b;
        else
            no.push_back(e);
    }
    
    pre[mp(1)] = -1;
    dfs(mp(1));
    
    //update with unused edges
    for(auto e: no){
        //lift
        int a = e.a, b = e.b;
        if(dep[a] < dep[b])
            swap(a, b);
        while(dep[a] > dep[b]){
            dp[a] = min(dp[a], e.c);
            a = pre[a];
        }
        while(a != b){
            dp[a] = min(dp[a], e.c);
            a = pre[a];
            dp[b] = min(dp[b], e.c);
            b = pre[b];
        }
    }
    
    ll sum = 0;
    
    for(int i = 0; i < k; i++){
        if(mask&(1<<i)){
            int a = mp(toll[i].a), b = mp(toll[i].b); //don't do find() bc not merging
            a = (dep[a] > dep[b] ? a : b);
            sum += dp[a]*compsz[a];
        }
    }
    ans = max(ans, sum);
}

int main(){
//    freopen("in.txt", "r", stdin);
    cin>>n>>m>>k;
    edges.resize(m);
    for(int i = 0,a,b,c; i < m; i++){
        cin>>a>>b>>c;
        edges[i] = {a, b, c};
    }
    reset();
    for(int i = 0,a,b; i < k; i++){
        cin>>a>>b;
        toll.push_back({a, b});
        par[find(a)] = find(b);
    }
    for(int i = 1; i <= n; i++)
        cin>>sz[i];
    sort(all(edges));
    
    for(auto e: edges){
        int a = find(e.a), b = find(e.b);
        if(a != b){
            par[a] = b;
            use.push_back(e);
//            cout<<"use "<<e.a<<' '<<e.b<<' '<<e.c<<endl;
        }
    }
    
    //second time without Ks
    reset();
    for(auto e: use){
        int a = find(e.a), b = find(e.b);
        par[a] = b;
    }
    
    //compress graph
    int t = 0;
    for(int i = 1; i <= n; i++){
        if(find(i) == i)
            compid[i] = t++;
    }
    
    for(int i = 1; i <= n; i++)
        compid[i] = compid[find(i)];
    
    for(int i = 1; i <= n; i++)
        compsz[compid[i]] += sz[i];
    
    // add maybe edges
    for(auto e: edges){
        int a = find(e.a), b = find(e.b);
        if(a != b){
            par[a] = b;
            
            a = mp(a), b = mp(b);
            adj[a].push_back(b);
            adj[b].push_back(a);
            
            maybe.push_back({a, b, e.c});
        }
    }
    edges.clear();
    edges.shrink_to_fit();
    
    for(int i = 0; i < (1<<k); i++)
        go(i);
    
    cout<<ans<<'\n';
    
    return 0;
}

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