oj.uz

Submission #889057

# Submission time Handle Problem Language Result Execution time Memory
889057 2023-12-18T18:01:10 Z vjudge1 Toll (APIO13_toll) C++17
100 / 100
 1229 ms 14160 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=1e5+9;
const int maxm=3e5+9;
long long val[maxn];
struct edg{
int u,v;
long long w;
bool operator < (const edg &p){
return w<p.w;
}
};
vector<edg>realneed;
edg b[maxm],c[20];
int num[maxn];
struct DSU{
vector<int>a;
int n;
void resz(int _n){
n=_n;
a.resize(n+1);
for1(i,1,n)a[i]=-1;
}
int findset(int u){
if (a[u]<0)return u;
return a[u]=findset(a[u]);
}
bool unite(int u,int v){
u=findset(u),v=findset(v);
if (u==v)return 0;
if (a[u]<a[v])swap(u,v);
a[u]+=a[v];
//val[u]+=val[v];
a[v]=u;
return 1;
}
};
long long sub[109];
int cc=0;
int n,m,k;
vector<pii>a[109];
long long newsub[109];
long long mmb[109];
int par[109];
int dis[109];
void dfs(int u,int p){
for (auto v:a[u]){
    if (v.fi==p)continue;
    par[v.fi]=u;
    if (!v.se)mmb[v.fi]=1e6;
    dis[v.fi]=dis[u]+1;
    dfs(v.fi,u);
    newsub[u]+=newsub[v.fi];
}
}
void minimize(edg temp){
int u=temp.u,v=temp.v;
while (dis[v]>dis[u]){
    mmb[v]=min(mmb[v],temp.w);
    v=par[v];
}
while (dis[u]>dis[v]){
    mmb[u]=min(mmb[u],temp.w);
    u=par[u];
}
while (u!=v){
    mmb[u]=min(mmb[u],temp.w);
    mmb[v]=min(mmb[v],temp.w);
    u=par[u];
    v=par[v];
}
 
}
long long cal(int mask){
    DSU temp;
    temp.resz(cc);
    for1(i,1,cc)a[i].clear();
    for1(i,1,cc){
    newsub[i]=sub[i];
    par[i]=0;
    mmb[i]=0;
    dis[i]=0;
    }
    for1(i,0,k-1){
    if (mask>>i&1){
        if (temp.unite(c[i].u,c[i].v)){
        a[c[i].u].pb({c[i].v,0});
        a[c[i].v].pb({c[i].u,0});
        }
        else return 0;
    }
    }
    vector<edg>notuse;
    for (auto v:realneed){
        if (temp.unite(v.u,v.v)){
            a[v.u].pb({v.v,1});
            a[v.v].pb({v.u,1});
        }
        else notuse.pb(v);
    }
    dfs(num[1],0);
    for (auto v:notuse){
        minimize(v);
        //cout<<v.u<<" "<<v.v<<" "<<v.w<<'\n';
    }
    long long ans=0;
    for1(i,1,cc){
        ans+=1ll*mmb[i]*newsub[i];
    }
    //cout<<mmb[1]<<" "<<newsub[1]<<'\n';
    return ans;
 
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    cin>>n>>m>>k;
    DSU m1,m2,real;
    m1.resz(n);
    m2.resz(n);
    real.resz(n);
    for1(i,1,m){
    cin>>b[i].u>>b[i].v>>b[i].w;
    }
    sort(b+1,b+1+m);
    for1(i,0,k-1){
    cin>>c[i].u>>c[i].v;
    }
    for1(i,1,n)cin>>val[i];
    for1(i,0,k-1){
    m1.unite(c[i].u,c[i].v);
    }
    for1(i,1,m){
    bool fl=false;
    if (real.unite(b[i].u,b[i].v)){
        fl=true;
    }
    if (m1.unite(b[i].u,b[i].v)){
        m2.unite(b[i].u,b[i].v);
        //cout<<b[i].u<<" "<<b[i].v<<'\n';
    }
    else {
        if (fl){
            realneed.pb(b[i]);
        }
    }
    }
    for1(i,1,n){
        if (m2.a[i]<0){
          num[i]=++cc;
        }
    }
    for1(i,1,n){
        num[i]=num[m2.findset(i)];
        sub[num[i]]+=val[i];
    }
    for1(i,0,k-1){
        c[i].u=num[c[i].u];
        c[i].v=num[c[i].v];
    }
    for (auto &v:realneed){
        v.u=num[v.u];
        v.v=num[v.v];
        //cout<<v.u<<" "<<v.v<<'\n';
    }
    long long ans=0;
    for1(i,0,(1<<k)-1){
    ans=max(ans,cal(i));
    }
    cout<<ans;
 
 
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 2616 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 2616 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 135 ms 13780 KB Output is correct
8 Correct 136 ms 13856 KB Output is correct
9 Correct 131 ms 13780 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 2616 KB Output is correct
6 Correct 3 ms 2396 KB Output is correct
7 Correct 135 ms 13780 KB Output is correct
8 Correct 136 ms 13856 KB Output is correct
9 Correct 131 ms 13780 KB Output is correct
10 Correct 952 ms 13960 KB Output is correct
11 Correct 1229 ms 13956 KB Output is correct
12 Correct 1211 ms 14160 KB Output is correct