oj.uz

Submission #1110156

# Submission time Handle Problem Language Result Execution time Memory
1110156 2024-11-08T21:55:16 Z vjudge1 Toll (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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