oj.uz

Submission #988199

# Submission time Handle Problem Language Result Execution time Memory
988199 2024-05-24T09:51:08 Z vjudge1 Toll (APIO13_toll) C++17
100 / 100
 1666 ms 27168 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 1<<17
#pragma GCC optimize(2)
vector<tuple<int,int,int>>adj_T,could;
vector<int>supa,adj[N];
vector<pair<int,bool>>adj2[N];
int par[N],R[N];
long long 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);
}
long long dfsA(int n,int p){
    long long 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 6 ms 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 9 ms 12892 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 9 ms 12892 KB Output is correct
5 Correct 6 ms 13144 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 9 ms 12892 KB Output is correct
5 Correct 6 ms 13144 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct
7 Correct 157 ms 21180 KB Output is correct
8 Correct 174 ms 19964 KB Output is correct
9 Correct 172 ms 21100 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 4 ms 12888 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 9 ms 12892 KB Output is correct
5 Correct 6 ms 13144 KB Output is correct
6 Correct 5 ms 13148 KB Output is correct
7 Correct 157 ms 21180 KB Output is correct
8 Correct 174 ms 19964 KB Output is correct
9 Correct 172 ms 21100 KB Output is correct
10 Correct 1134 ms 20148 KB Output is correct
11 Correct 1666 ms 19924 KB Output is correct
12 Correct 1590 ms 27168 KB Output is correct