oj.uz

Submission #889891

# Submission time Handle Problem Language Result Execution time Memory
889891 2023-12-20T09:12:10 Z vjudge1 Toll (APIO13_toll) C++17
100 / 100
 1410 ms 35504 KB 
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx,avx2,fma")
#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 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 5 ms 13024 KB Output is correct
6 Correct 4 ms 13024 KB Output is correct
7 Correct 139 ms 34860 KB Output is correct
8 Correct 146 ms 34732 KB Output is correct
9 Correct 140 ms 34224 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 5 ms 13024 KB Output is correct
6 Correct 4 ms 13024 KB Output is correct
7 Correct 139 ms 34860 KB Output is correct
8 Correct 146 ms 34732 KB Output is correct
9 Correct 140 ms 34224 KB Output is correct
10 Correct 1084 ms 33904 KB Output is correct
11 Correct 1391 ms 35504 KB Output is correct
12 Correct 1410 ms 33828 KB Output is correct