Submission #366222

#	Time	Username	Problem	Language	Result	Execution time	Memory
366222		zaneyu	Toll (APIO13_toll)	C++14	100 / 100	1939 ms	18000 KiB

toll

/*input
30 50 10
24 16 369496
5 2 882195
24 23 579700
24 1 795457
7 10 903779
13 21 98625
27 24 857438
2 26 795121
21 15 117380
10 6 168591
12 2 439190
4 3 631680
18 24 785210
2 16 558732
22 26 215162
4 2 399966
15 2 203973
1 30 206852
12 10 263496
28 29 122008
6 19 593874
1 28 729019
11 14 346091
11 13 859391
9 3 250786
14 17 58750
20 30 715721
8 17 76276
16 25 503808
9 23 608485
20 26 177123
20 24 76108
9 11 461717
4 29 61938
3 23 405937
4 12 629269
20 9 468405
26 11 810260
11 28 909762
8 16 132851
6 29 131309
19 2 893460
7 4 900573
2 23 501910
27 7 17890
15 6 89374
9 18 768191
9 4 146599
14 13 493053
27 30 363411
21 16
29 17
4 16
9 15
14 21
8 15
8 14
11 17
16 11
15 14
98495 451898 635349 718145 736138 934033 499900 806636 576111 865528 987596 221117 291484 516779 773713 197649 986173 849511 37913 201286 988480 239850 542833 764343 952464 230577 64037 976130 291804 150520

*/
#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 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,u2;
vector<pii> v[maxn];
vector<int> g[25];
int comp[maxn];
ll par[25],pae[25],dep[25],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(int x:g[u]){
        if(x!=p){
            dep[x]=dep[u]+1;
            par[x]=u;
            pae[x]=INF;
            dfs2(x,u);
            tmp[u]+=tmp[x];
        }
    }
}
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(n),u2.init(cnt+1);
    vector<pair<int,pii>> left;
    for(auto x:edge){
        int a=x.s.f,b=x.s.s;
        if(uf.find(a)!=uf.find(b)){
            uf.merge(a,b);
        }
        else{
            if(u2.find(comp[a])!=u2.find(comp[b])){
                if(x.f==-INF) continue;
                u2.merge(comp[a],comp[b]);
                left.pb({x.f,{comp[a],comp[b]}});
               // cout<<x.f<<' '<<comp[a]<<' '<<comp[b]<<'\n';
            }
        }
    }
    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) g[j].clear(),tmp[j]=csz[j];
        uf.init(cnt+1);
        bool die=0;
        REP(i,k){
            if(msk&(1<<i)){
                if(uf.find(nw[i].f)==uf.find(nw[i].s)){
                    die=1;
                    break;
                }
                uf.merge(nw[i].f,nw[i].s);
                g[nw[i].f].pb(nw[i].s);
                g[nw[i].s].pb(nw[i].f);
            } 
        }
        if(die) continue;
        vector<pair<int,pii>> l2;
        for(auto x:left){
            if(uf.find(x.s.f)!=uf.find(x.s.s)){
                uf.merge(x.s.f,x.s.s);
                g[x.s.f].pb(x.s.s);
                g[x.s.s].pb(x.s.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: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22