Submission #986254

#	Time	Username	Problem	Language	Result	Execution time	Memory
986254		vjudge1	Toll (APIO13_toll)	C++17	16 / 100	5 ms	604 KiB

toll

#include<bits/stdc++.h>
using namespace std;
#define N 7<<10
#define int long long
vector<int> E,EEE;
set<pair<int,int>>adj[N];
int U[N],V[N],W[N],P[N],K,par[N],rem[N],res,ans;
int abp(int n){
    if(par[n]==n)
        return n;
    return par[n]=abp(par[n]);
}
bool dfs(int n,int p,int t){
    if(n==t)
        return 1;
    for(auto[i,j]:adj[n]){
        if(i==p)continue;
        if(dfs(i,n,t)) {
            if(W[res]<W[j])
                res=j;
            return 1;
        }
    }
    return 0;
}
void calc(int n,int p,int t){
    res+=P[n]*t;
    for(auto[i,j]:adj[n])if(i-p)
        calc(i,n,t+W[j]*(j<K));
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n>>m>>K;
    while(m--) {
        cin>>U[m+K]>>V[m+K]>>W[m+K];
        E.push_back(m+K);
    }
    for(int i=0;i<K;i++)
        cin>>U[i]>>V[i];
    for(int i=0;i<n;)
        cin>>P[++i],par[i]=i;
    sort(E.begin(),E.end(),[](int a,int b){return W[a]<W[b];});
    for(auto i:E)
        if(abp(U[i])-abp(V[i]))
            par[par[U[i]]]=par[V[i]],
            EEE.push_back(i);
    E=EEE;
    for(auto i:E)
        adj[U[i]].insert({V[i],i}),
        adj[V[i]].insert({U[i],i});
    for(m=1;m<1<<K;m++){
        vector<int>R,ve;
        for(int i=1;i<=n;i++)
            par[i]=i;
        for(auto i:E)
            rem[i]=0;
        for(int i=0;i<K;W[i++]=0)if(m&1<<i)
            ve.push_back(i);
        int fail=0;
        for(auto i:ve){
            int a=abp(U[i]),b=abp(V[i]);
            if(a==b){fail=1;break;}
            par[a]=b;
        }
        if(fail)continue;
        for(int i=1;i<=n;i++)
            par[i]=i;
        for(auto i:ve){
            dfs(U[i],0,V[i]),R.push_back(res);
            adj[U[i]].insert({V[i],i});
            adj[V[i]].insert({U[i],i});
            adj[U[res]].erase({V[res],res});
            adj[V[res]].erase({U[res],res});
            rem[res]=1,res=0;
        }
        for(auto j:E)
            if(rem[j]){
                int a=abp(U[j]),b=abp(V[j]);
                if(a>b)swap(a,b);
                while(1){
                    int ok=0;
                    for(auto i:ve){
                        int c=abp(U[i]),d=abp(V[i]);
                        if(c>d)swap(c,d);
                        if(a==c&&b==d){
                            W[i]=W[j];
                            par[c]=d;
                            ok=1;
                            break;
                        }
                    }
                    if(!ok)
                        break;
                }
            } else par[abp(U[j])]=par[abp(V[j])];
        calc(1,0,0);
        ans=max(ans,res);
        res=0;
        for(auto i:R)adj[U[i]].insert({V[i],i}),
            adj[V[i]].insert({U[i],i});
        for(auto i:ve) adj[U[i]].erase({V[i],i}),
            adj[V[i]].erase({U[i],i});
    }
    cout<<ans;
}

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