Submission #889884

#	Time	Username	Problem	Language	Result	Execution time	Memory
889884		amogususus	Toll (APIO13_toll)	C++17	100 / 100	1481 ms	41936 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[44],id[maxN],weight[44],s,val[44],edge[44],par[44],d[44];
ll fset(ll x){return lab[x]<0?x:lab[x]=fset(lab[x]);}
bool 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;
        return 1;
    }
    return 0;
}
struct edg{
    ll u,v,w,id;
    bool operator<(const edg&o){return w<o.w;}
};
vector<edg> cho,dit,dai,cac,lon;
vector<pll> adj[maxN];
void pre(ll u,ll p=1){
    par[u]=p;
    for(auto x:adj[u])if(x.first!=p){
        ll v=x.first,w=weight[x.second];
        edge[v]=x.second;
        d[v]=d[u]+1;
        pre(v,u);
    }
}
void dfs(ll u,ll p=1){
    val[u]=sum[u];
    for(auto x:adj[u])if(x.first!=p){
        ll v=x.first,w=weight[x.second];
        dfs(v,u);
        val[u]+=val[v];
        s+=w*val[v];
    }
}
void cut(ll u,ll v,ll w){
    while(u!=v){
        if(d[u]<d[v])swap(u,v);
        weight[edge[u]]=min(weight[edge[u]],w);
        u=par[u];
    }
}
ll vis[maxN];
bool mst[maxN];
void Enter(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        ll u,v,w;cin>>u>>v>>w;
        cho.pb({u,v,w,i});
    }
    for(int i=1;i<=k;i++){
        ll u,v;cin>>u>>v;
        dit.pb({u,v,-1,i});
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(all(cho));

    memset(lab,-1,sizeof lab);
    for(auto&x:cho)if(uset(x.u,x.v))mst[x.id]=1;

    memset(lab,-1,sizeof lab);
    for(auto&y:dit)uset(y.u,y.v);
    for(auto&x:cho)
        if(uset(x.u,x.v))dai.pb(x);
        else if(mst[x.id])lon.pb(x);

    memset(lab,-1,sizeof lab);
    for(auto&x:dai)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:cho)x.u=id[x.u],x.v=id[x.v];
    for(auto&x:lon)x.u=id[x.u],x.v=id[x.v];

    memset(lab,-1,44*sizeof(ll));
    for(auto&x:cho)if(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));
        memset(weight,1,sizeof weight);
        weight[0]=0;
        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)if(uset(dit[i].u,dit[i].v))adj[dit[i].u].pb({dit[i].v,i+1}),adj[dit[i].v].pb({dit[i].u,i+1});
        vector<edg> xeo;
        for(auto&x:lon)
            if(uset(x.u,x.v))adj[x.u].pb({x.v,0}),adj[x.v].pb({x.u,0});
            else xeo.pb(x);
        pre(id[1]);
        for(auto&x:xeo)cut(x.u,x.v,x.w);
        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();
}

Compilation message (stderr)

toll.cpp: In function 'void pre(long long int, long long int)':
toll.cpp:36:22: warning: unused variable 'w' [-Wunused-variable]
   36 |         ll v=x.first,w=weight[x.second];
      |                      ^

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