oj.uz

Submission #889884

# Submission time Handle Problem Language Result Execution time Memory
889884 2023-12-20T08:57:21 Z amogususus Toll (APIO13_toll) C++17
100 / 100
 1481 ms 41936 KB 
#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

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.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12628 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 5 ms 13024 KB Output is correct
6 Correct 5 ms 13024 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12628 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 5 ms 13024 KB Output is correct
6 Correct 5 ms 13024 KB Output is correct
7 Correct 167 ms 41924 KB Output is correct
8 Correct 173 ms 40952 KB Output is correct
9 Correct 173 ms 41876 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12628 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 4 ms 12632 KB Output is correct
4 Correct 4 ms 12636 KB Output is correct
5 Correct 5 ms 13024 KB Output is correct
6 Correct 5 ms 13024 KB Output is correct
7 Correct 167 ms 41924 KB Output is correct
8 Correct 173 ms 40952 KB Output is correct
9 Correct 173 ms 41876 KB Output is correct
10 Correct 1143 ms 41656 KB Output is correct
11 Correct 1481 ms 41936 KB Output is correct
12 Correct 1449 ms 40488 KB Output is correct