oj.uz

답안 #1110156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1110156 2024-11-08T21:55:16 Z vjudge1 통행료 (APIO13_toll) C++17
100 / 100
 1526 ms 32420 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define N 1<<17
vector<tuple<int,int,int>>adj_T,could;
vector<int>supa,adj[N];
vector<pair<int,bool>>adj2[N];
int par[N],R[N],peop[N],ans,A;
bitset<1<<20>good,vis;
priority_queue<int,vector<int>,greater<int>>S[N];
vector<pair<int,int>> adj_G;
int abp(int x){
    if(par[x])
        return par[x]=abp(par[x]);
    return x;
}
bool unite(int a,int b){
    a=abp(a),b=abp(b);
    if(a-b)
        par[a]=b;
    return a!=b;
}
void dfs(int n,int rt){
    if(vis[n])return;
    vis[n]=1,R[n]=rt;
    peop[rt]+=(n>rt)*peop[n];
    for(auto i:adj[n])
        dfs(i,rt);
}
int dfsA(int n,int p){
    int sum=peop[n],q;
    for(auto[i,j]:adj2[n]){
        if(i==p)continue;
        q=dfsA(i,n);
        sum+=q;
        if(S[i].empty())continue;
        int K=S[i].top();
        S[i].pop();
        while(S[i].size()&&S[i].top()==K) {
            S[i].pop(),K=S[i].top();
            if(S[i].size())S[i].pop();
        }
        S[i].push(K);
        ans+=j*q*K;
        if(S[i].size()>S[n].size())
            swap(S[i],S[n]);
        while(S[i].size())
            S[n].push(S[i].top()),S[i].pop();
    }
    return sum;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=m;i--;){
        int a,b,c;
        cin>>a>>b>>c;
        adj_T.push_back({a,b,c});
    }
    for(int i=0;i<k;i++){
        int a,b;
        cin>>a>>b;
        adj_G.push_back({a,b});
    }
    for(int i=1;i<=n;i++)
        cin>>peop[i];
    for(auto[i,j]:adj_G)
        unite(i,j);
    sort(adj_T.begin(),adj_T.end(),[](tuple<int,int,int>a,tuple<int,int,int>b){
        return get<2>(a)<get<2>(b);
    });
    for(auto[i,j,w]:adj_T) if(unite(i,j))
        good[w]=1,adj[i].push_back(j),
        adj[j].push_back(i);
    for(int i=1;i<=n;i++)
        par[i]=0;
    for(auto[i,j,w]:adj_T)
        if(unite(i,j)&&!good[w])
            could.push_back({i,j,w});
    for(int i=1;i<=n;i++)
        if(!vis[i])dfs(i,i),
        supa.push_back(i);
    for(auto&[i,j]:adj_G)
        i=R[i],j=R[j];
    for(auto&[i,j,w]:could)
        i=R[i],j=R[j];
    for(int i=1;i<1<<k;i++){
        for(auto i:supa)
            adj2[i].clear(),par[i]=0;
        int ok=1;
        for(int j=0;j<k;j++) if(i&1<<j)
            ok&=unite(adj_G[j].first,adj_G[j].second),
            adj2[adj_G[j].first].push_back({adj_G[j].second,1}),
            adj2[adj_G[j].second].push_back({adj_G[j].first,1});
        if(!ok) continue;
        for(auto[i,j,w]:could) if(!unite(i,j))
            S[i].push(w),S[j].push(w);
        else adj2[i].push_back({j,0}),
            adj2[j].push_back({i,0});
        dfsA(1,0);
        A=max(A,ans);
        ans=0;
        while(S[1].size())
            S[1].pop();
    }
    cout<<A<<'\n';
}

Subtask #1
16.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13904 KB Output is correct
2 Correct 4 ms 13904 KB Output is correct
3 Correct 5 ms 13904 KB Output is correct
4 Correct 5 ms 13988 KB Output is correct
5 Correct 6 ms 14352 KB Output is correct
6 Correct 5 ms 14352 KB Output is correct
7 Correct 148 ms 32100 KB Output is correct
8 Correct 165 ms 32328 KB Output is correct
9 Correct 166 ms 32144 KB Output is correct

Subtask #5
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 13904 KB Output is correct
2 Correct 4 ms 13904 KB Output is correct
3 Correct 5 ms 13904 KB Output is correct
4 Correct 5 ms 13988 KB Output is correct
5 Correct 6 ms 14352 KB Output is correct
6 Correct 5 ms 14352 KB Output is correct
7 Correct 148 ms 32100 KB Output is correct
8 Correct 165 ms 32328 KB Output is correct
9 Correct 166 ms 32144 KB Output is correct
10 Correct 1098 ms 32344 KB Output is correct
11 Correct 1526 ms 32364 KB Output is correct
12 Correct 1473 ms 32420 KB Output is correct