제출 #366201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366201		zaneyu	통행료 (APIO13_toll)	C++14	16 / 100	122 ms	163844 KiB

toll

/*input
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("unroll-loo8ps,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ll long long
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FIlim(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const ll INF=0x3f3f3f3f;
const ll MOD=1e9+7;
//const ld PI=acos(-1);
const ld eps=1e-9;
const int maxn=1e5+5;
const int maxlg=__lg(maxn)+2;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define FILL(x,y) memset(x,y,sizeof(x))
inline ll mult(ll a,ll b){
    a%=MOD,b%=MOD;
    return (a*b)%MOD;
}
inline ll mypow(ll a,ll b){
    if(b<=0) return 1;
    a%=MOD;
    ll res=1;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
ll st[maxn];
ll csz[maxn];
ll tmp[maxn];
struct UFDS{
    int par1[maxn];
    void init(int n){
        REP(i,n) par1[i]=i;
    }
    int find(int u){
        if(par1[u]==u) return par1[u];
        return par1[u]=find(par1[u]);
    }
    void merge(int a,int b){
        a=find(a),b=find(b);
        par1[a]=b;
    }
}uf;
vector<pii> v[maxn];
vector<pii> g[maxn];
int comp[maxn];
int par[maxn],pae[maxn],dep[maxn],arr[maxn];
void dfs(int u,int c){
    csz[c]+=arr[u];
    for(auto x:v[u]){
        if(!comp[x.f]){
            comp[x.f]=c;
            dfs(x.f,c);
        }
    }
}
void dfs2(int u,int p){
    for(auto x:v[u]){
        if(x.f!=p){
            dep[x.f]=dep[u]+1;
            par[x.f]=u;
            pae[x.f]=INF;
            dfs2(x.f,u);
            tmp[u]+=tmp[x.f];
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<pair<int,pii>> edge;
    
    REP(i,m){
        int a,b,c;
        cin>>a>>b>>c;
        --a;
        --b;
        edge.pb({c,{a,b}});
    }
    uf.init(n);
    ll ans=0;
    vector<pii> nw;
    REP(i,k){
        int a,b;
        cin>>a>>b;
        --a;
        --b;
        nw.pb({a,b});
        edge.pb({-INF,{a,b}});
    }
    sort(ALL(edge));
    REP(i,n) cin>>arr[i];
    for(auto x:edge){
        int a=x.s.f,b=x.s.s;
        if(uf.find(a)!=uf.find(b)){
            uf.merge(a,b);
            if(x.f!=-INF){
                v[a].pb({b,x.f});
                v[b].pb({a,x.f});
            }  
        }
    }
    int cnt=0;
    REP(i,n){
        if(!comp[i]){
            comp[i]=++cnt;
            dfs(i,cnt);
        }
    }
    uf.init(cnt+1);
    vector<pair<int,pii>> left;
    for(auto x:edge){
        int a=x.s.f,b=x.s.s;
        if(comp[a]==comp[b] or x.f==-INF) continue;
        if(uf.find(comp[a])!=uf.find(comp[b])){
            uf.merge(comp[a],comp[b]);
            if(x.f!=-INF){
                left.pb({x.f,{comp[a],comp[b]}});
            }  
        }
    }
    for(auto &x:nw) x.f=comp[x.f],x.s=comp[x.s];
    REP(i,n) v[i].clear(),v[i].shrink_to_fit();

    REP1(msk,(1<<k)-1){
        REP(j,cnt+1) v[j].clear(),tmp[j]=csz[j];
        uf.init(cnt+1);
        REP(i,k){
            if(msk&(1<<i)){
                uf.merge(nw[i].f,nw[i].s);
                v[nw[i].f].pb({nw[i].s,edge[i].f});
                v[nw[i].s].pb({nw[i].f,edge[i].f});
            } 
        }
        vector<pair<int,pii>> l2;
        for(auto x:left){
            if(uf.find(x.s.f)!=uf.find(x.s.s)){
                v[x.s.f].pb({x.s.s,x.f});
                v[x.s.s].pb({x.s.f,x.f});
            } 
            else{
                l2.pb(x);
            }
        }
        dfs2(1,-1);
        for(auto x:l2){
            int a=x.s.f,b=x.s.s;
            if(dep[a]<dep[b]) swap(a,b);
            while(dep[a]<dep[b]){
                MNTO(pae[a],x.f);
                a=par[a];
            }
            while(a!=b){
                MNTO(pae[a],x.f);
                MNTO(pae[b],x.f);
                a=par[a];
                b=par[b];
            }
        }
        ll cur=0;
        REP(i,k){
            if(msk&(1<<i)){
                if(tmp[nw[i].f]>tmp[nw[i].s]) swap(nw[i].f,nw[i].s);
                cur+=tmp[nw[i].f]*pae[nw[i].f];
            }
        }
        MXTO(ans,cur);
    }
    cout<<ans;
}

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