Submission #752809

#	Time	Username	Problem	Language	Result	Execution time	Memory
752809		winter0101	Toll (APIO13_toll)	C++14	100 / 100	1618 ms	13900 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=1e5+9;
const int maxm=3e5+9;
long long val[maxn];
struct edg{
int u,v;
long long w;
bool operator < (const edg &p){
return w<p.w;
}
};
vector<edg>realneed;
edg b[maxm],c[20];
int num[maxn];
struct DSU{
vector<int>a;
int n;
void resz(int _n){
n=_n;
a.resize(n+1);
for1(i,1,n)a[i]=-1;
}
int findset(int u){
if (a[u]<0)return u;
return a[u]=findset(a[u]);
}
bool unite(int u,int v){
u=findset(u),v=findset(v);
if (u==v)return 0;
if (a[u]<a[v])swap(u,v);
a[u]+=a[v];
//val[u]+=val[v];
a[v]=u;
return 1;
}
};
long long sub[109];
int cc=0;
int n,m,k;
vector<pii>a[109];
long long newsub[109];
long long mmb[109];
int par[109];
int dis[109];
void dfs(int u,int p){
for (auto v:a[u]){
    if (v.fi==p)continue;
    par[v.fi]=u;
    if (!v.se)mmb[v.fi]=1e6;
    dis[v.fi]=dis[u]+1;
    dfs(v.fi,u);
    newsub[u]+=newsub[v.fi];
}
}
void minimize(edg temp){
int u=temp.u,v=temp.v;
while (dis[v]>dis[u]){
    mmb[v]=min(mmb[v],temp.w);
    v=par[v];
}
while (dis[u]>dis[v]){
    mmb[u]=min(mmb[u],temp.w);
    u=par[u];
}
while (u!=v){
    mmb[u]=min(mmb[u],temp.w);
    mmb[v]=min(mmb[v],temp.w);
    u=par[u];
    v=par[v];
}

}
long long cal(int mask){
    DSU temp;
    temp.resz(cc);
    for1(i,1,cc)a[i].clear();
    for1(i,1,cc){
    newsub[i]=sub[i];
    par[i]=0;
    mmb[i]=0;
    dis[i]=0;
    }
    for1(i,0,k-1){
    if (mask>>i&1){
        if (temp.unite(c[i].u,c[i].v)){
        a[c[i].u].pb({c[i].v,0});
        a[c[i].v].pb({c[i].u,0});
        }
        else return 0;
    }
    }
    vector<edg>notuse;
    for (auto v:realneed){
        if (temp.unite(v.u,v.v)){
            a[v.u].pb({v.v,1});
            a[v.v].pb({v.u,1});
        }
        else notuse.pb(v);
    }
    dfs(num[1],0);
    for (auto v:notuse){
        minimize(v);
        //cout<<v.u<<" "<<v.v<<" "<<v.w<<'\n';
    }
    long long ans=0;
    for1(i,1,cc){
        ans+=1ll*mmb[i]*newsub[i];
    }
    //cout<<mmb[1]<<" "<<newsub[1]<<'\n';
    return ans;

}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    cin>>n>>m>>k;
    DSU m1,m2,real;
    m1.resz(n);
    m2.resz(n);
    real.resz(n);
    for1(i,1,m){
    cin>>b[i].u>>b[i].v>>b[i].w;
    }
    sort(b+1,b+1+m);
    for1(i,0,k-1){
    cin>>c[i].u>>c[i].v;
    }
    for1(i,1,n)cin>>val[i];
    for1(i,0,k-1){
    m1.unite(c[i].u,c[i].v);
    }
    for1(i,1,m){
    bool fl=false;
    if (real.unite(b[i].u,b[i].v)){
        fl=true;
    }
    if (m1.unite(b[i].u,b[i].v)){
        m2.unite(b[i].u,b[i].v);
        //cout<<b[i].u<<" "<<b[i].v<<'\n';
    }
    else {
        if (fl){
            realneed.pb(b[i]);
        }
    }
    }
    for1(i,1,n){
        if (m2.a[i]<0){
          num[i]=++cc;
        }
    }
    for1(i,1,n){
        num[i]=num[m2.findset(i)];
        sub[num[i]]+=val[i];
    }
    for1(i,0,k-1){
        c[i].u=num[c[i].u];
        c[i].v=num[c[i].v];
    }
    for (auto &v:realneed){
        v.u=num[v.u];
        v.v=num[v.v];
        //cout<<v.u<<" "<<v.v<<'\n';
    }
    long long ans=0;
    for1(i,0,(1<<k)-1){
    ans=max(ans,cal(i));
    }
    cout<<ans;


}

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