oj.uz

답안 #726327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
726327 2023-04-18T18:01:40 Z vjudge1 통행료 (APIO13_toll) C++17
100 / 100
 1679 ms 13824 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 440 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 440 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 183 ms 7480 KB Output is correct
8 Correct 181 ms 7368 KB Output is correct
9 Correct 189 ms 7356 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 440 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 183 ms 7480 KB Output is correct
8 Correct 181 ms 7368 KB Output is correct
9 Correct 189 ms 7356 KB Output is correct
10 Correct 1369 ms 7372 KB Output is correct
11 Correct 1677 ms 13760 KB Output is correct
12 Correct 1679 ms 13824 KB Output is correct