oj.uz

Submission #752809

# Submission time Handle Problem Language Result Execution time Memory
752809 2023-06-04T01:37:41 Z winter0101 Toll (APIO13_toll) C++14
100 / 100
 1618 ms 13900 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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 484 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 174 ms 13820 KB Output is correct
8 Correct 176 ms 13772 KB Output is correct
9 Correct 171 ms 13900 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 174 ms 13820 KB Output is correct
8 Correct 176 ms 13772 KB Output is correct
9 Correct 171 ms 13900 KB Output is correct
10 Correct 1267 ms 13824 KB Output is correct
11 Correct 1618 ms 13824 KB Output is correct
12 Correct 1554 ms 13864 KB Output is correct