Submission #872891

#	Time	Username	Problem	Language	Result	Execution time	Memory
872891		gggkik	Toll (APIO13_toll)	C++14	16 / 100	2 ms	5980 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct dsu{
    vector<int> par;
    void init(int x){
        par.resize(x+1);
        iota(par.begin(),par.end(),0);
    }
    int find(int x){
        return par[x]-x?par[x]=find(par[x]):x;
    }
    void u(int a,int b){
        a = find(a), b = find(b);
        if(a!=b) par[a] = b;
    }
};
vector<vector<int>> build_mst(int n, vector<vector<int>> edges){
    dsu uf; uf.init(n);
    sort(edges.begin(),edges.end(),[&](vector<int> &i, vector<int> &j){
        return i[2]<j[2];
    });
    vector<vector<int>> ret;
    for(auto &i : edges){
        int a = uf.find(i[0]), b = uf.find(i[1]);
        if(a!=b) {
            uf.u(a,b);
            ret.push_back(i);
        }
    }
    return ret;
}
const int MXN = 1e5+5;
using pii = pair<int,int>;
using ll = long long;
vector<pii> E[MXN];
void build(int n,vector<vector<int>> &v){
    for(int i = 1;i<=n;i++) E[i].clear();
    for(auto &j : v){
        E[j[0]].push_back({j[1],j[2]});
        E[j[1]].push_back({j[0],j[2]});
    }
}
ll sz[MXN], A[MXN], P[MXN];
int h[MXN], par[MXN], ck[MXN];
void dfs(int x,int p){
    sz[x] = A[x];
    par[x] = p;
    h[x] = h[p]+1;
    for(auto i : E[x]) if(i.first!=p){
        P[i.first] = i.second;
        dfs(i.first,x);
        sz[x] += sz[i.first];
    }
}
int lca(int a,int b){
    int mxp = 0;
    while(a!=b){
        if(h[a]<h[b]) swap(a,b);
        if(P[mxp]<P[a]) mxp = a;
        a = par[a];
    }
    return mxp;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>> edges;
    for(int i = 0;i<m;i++){
        int a,b,c; cin >> a >> b >> c;
        edges.push_back({a,b,c});
    }
    vector<vector<int>> myedge;
    for(int i = 0;i<k;i++){
        int a,b; cin >> a >> b;
        myedge.push_back({a,b,0});
    }
    for(int i = 1;i<=n;i++) cin >> A[i];
    edges = build_mst(n, edges);
    build(n, edges); dfs(1,0);
    ll ans = 0;
    for(int i = 0;i<1<<k;i++){
        ll cost = 0;
        vector<int> v;
        for(int j = 0;j<k;j++) if(i>>j&1)
            v.push_back(lca(myedge[j][0],myedge[j][1]));
        int no = 0;
        for(int j : v){
            if(ck[j]) no = 1;
            cost += P[j]*sz[j];
            ck[j] = 1;
        }
        for(int j : v) ck[j] = 0;
        if(no) continue;
        ans = max(cost,ans);
    }
    cout << ans;
}

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