oj.uz

Submission #366222

# Submission time Handle Problem Language Result Execution time Memory
366222 2021-02-13T14:29:16 Z zaneyu Toll (APIO13_toll) C++14
100 / 100
 1939 ms 18000 KB 
/*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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 5 ms 2924 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 5 ms 2924 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct
7 Correct 233 ms 17872 KB Output is correct
8 Correct 246 ms 17872 KB Output is correct
9 Correct 267 ms 17872 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2668 KB Output is correct
4 Correct 3 ms 2668 KB Output is correct
5 Correct 5 ms 2924 KB Output is correct
6 Correct 5 ms 2924 KB Output is correct
7 Correct 233 ms 17872 KB Output is correct
8 Correct 246 ms 17872 KB Output is correct
9 Correct 267 ms 17872 KB Output is correct
10 Correct 1589 ms 18000 KB Output is correct
11 Correct 1939 ms 17872 KB Output is correct
12 Correct 1923 ms 17872 KB Output is correct