Submission #889148

#	Time	Username	Problem	Language	Result	Execution time	Memory
889148		amogususus	Toll (APIO13_toll)	C++17	16 / 100	6 ms	18780 KiB

toll

#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,fma,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define bit(x,i) (x>>i&1)
using namespace std;
const int maxN=3e5+69;
const int mod=1e9+7;
const int base=311;
ll n,m,k,a[maxN],lab[maxN],sum[maxN],id[maxN];
ll fset(ll x){return lab[x]<0?x:lab[x]=fset(lab[x]);}
void uset(ll x,ll y){
    if((x=fset(x))!=(y=fset(y))){
        if(lab[x]>lab[y])swap(x,y);
        lab[x]+=lab[y];
        lab[y]=x;
    }
}
struct edg{
    ll u,v,w;
    bool operator<(const edg&o){
        return w<o.w;
    }
};
vector<edg> edge,dit,must,cac;
vector<pll> adj[maxN];
ll s=0;
ll val[maxN];
void dfs(ll u,ll p=0){
    val[u]=sum[u];
    for(auto x:adj[u])if(x.first!=p){
        ll v=x.first,w=x.second;
        dfs(v,u);
        val[u]+=val[v];
        s+=w*val[v];
    }
}
ll vis[maxN];
void Enter(){
    memset(lab,-1,sizeof lab);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        ll u,v,w;cin>>u>>v>>w;
        edge.pb({u,v,w});
    }
    for(int i=1;i<=k;i++){
        ll u,v;cin>>u>>v;
        dit.pb({u,v,-1});
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(all(edge));
    for(auto&x:edge){
        ll u=fset(x.u),v=fset(x.v);
        if(u==v)continue;
        if(u>v)swap(u,v);
        for(auto&y:dit){
            ll p=fset(y.u),q=fset(y.v);
            if(p==q)continue;
            if(p>q)swap(p,q);
            if(u==p&&v==q)y.w=x.w;
        }
        uset(u,v);
    }
    memset(lab,-1,sizeof lab);
    for(auto y:dit)uset(y.u,y.v);
    for(auto x:edge){
        if(fset(x.u)==fset(x.v))continue;
        must.pb(x);
        uset(x.u,x.v);
    }
    memset(lab,-1,sizeof lab);
    for(auto x:must)uset(x.u,x.v);
    ll cnt=0;
    for(int i=1;i<=n;i++){
        if(!vis[fset(i)])vis[fset(i)]=++cnt;
        id[i]=vis[fset(i)];
        sum[id[i]]+=a[i];
    }
    for(auto&x:dit)x.u=id[x.u],x.v=id[x.v];
    for(auto&x:edge)x.u=id[x.u],x.v=id[x.v];
    memset(lab,-1,44*sizeof(ll));
    for(auto&x:edge)if(fset(x.u)!=fset(x.v))uset(x.u,x.v),cac.pb(x);
    ll r=0;
    for(int mask=1;mask<(1<<k);mask++){
        memset(lab,-1,44*sizeof(ll));
        s=0;
        for(int i=1;i<=40;i++)adj[i].clear(),val[i]=0;
        for(int i=0;i<k;i++)if(mask>>i&1)uset(dit[i].u,dit[i].v),adj[dit[i].u].pb({dit[i].v,dit[i].w}),adj[dit[i].v].pb({dit[i].u,dit[i].w});
        for(auto&x:cac)if(fset(x.u)!=fset(x.v))uset(x.u,x.v),adj[x.u].pb({x.v,0}),adj[x.v].pb({x.u,0});
        dfs(id[1]);
        r=max(r,s);
    }
    cout<<r;
}
//amogus
signed main(){
    //open("MSEQ");
    cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
    //ll t=1;cin>>t;while(t--)
    Enter();
}

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