제출 #872933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872933		gggkik	통행료 (APIO13_toll)	C++14	0 / 100	4 ms	12380 KiB

toll

#include <bits/stdc++.h>
using namespace std;
const int MXN = 1e5+5;
using pii = pair<int,int>;
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;
}
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 A[MXN], P[MXN];
int h[MXN], par[MXN];
void dfs(int x,int p){
    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);
    }
}
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 L[MXN], ck[MXN], rt[MXN], rpar[MXN], vis[MXN];
set<pii> G[MXN];
ll sz[MXN];
void f(int x,int r,int p){
    rt[x] = r;
    sz[r] += A[x];
    for(auto &i : E[x]) if(i.first!=p){
        if(ck[i.first]) {
            rpar[i.first] = r;
            G[r].insert(i);
            //cout << r << "->" << i.first << endl;
            f(i.first,i.first,x);
        }
        else {
            f(i.first,r,x);
        }
    }
}
pair<ll,ll> get(int x){
    pair<ll,ll> ret = {0,sz[x]};
    for(auto &i : G[x]) {
        pair<ll,ll> res = get(i.first);
        ret.second += res.second;
        ret.first += res.first;
        if(vis[i.first]) ret.first += res.second*i.second;
    }
    //cout << "!!" << x << ' ' << ret.first << ' ' << ret.second << endl; 
    return ret;
}
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);
    for(int i = 0;i<k;i++){
        L[i] = lca(myedge[i][0],myedge[i][1]);
        ck[L[i]] = 1;
        //cout << L[i] << "~\n";
    }
    f(1,1,0);
    //for(int i = 1;i<=n;i++) cout << sz[i] << ' '; cout << '\n';
    ll ans = 0;
    for(int i = 0;i<1<<k;i++){
        vector<int> v;
        for(int j = 0;j<k;j++) if(i>>j&1)
            v.push_back(L[j]);
        int no = 0;
        for(int j : v){
            if(vis[j]) no = 1;
            vis[j] = 1;
        }
        if(no) {
            for(int j : v) vis[j] = 0;
            continue;
        }
        for(int j = 0;j<k;j++) if(i>>j&1){
            int u = myedge[j][0], v = myedge[j][1];
            if(h[u]>h[v]) swap(u,v);
            int a = L[j];
            G[rpar[a]].erase({a,P[a]});
            G[rt[u]].insert({rt[v],P[a]});
        }
        ll cost = get(1).first;
        for(int j = 0;j<k;j++) if(i>>j&1){
            int u = myedge[j][0], v = myedge[j][1];
            if(h[u]>h[v]) swap(u,v);
            int a = L[j];
            G[rpar[a]].insert({a,P[a]});
            G[rt[u]].erase({rt[v],P[a]});
        }
        //cout << i << " :: ";
        //cout << cost << endl;
        ans = max(cost,ans);
        for(int j : v) vis[j] = 0;
    } 
    cout << ans;
}

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