oj.uz

Submission #988208

# Submission time Handle Problem Language Result Execution time Memory
988208 2024-05-24T09:53:29 Z boyliguanhan Toll (APIO13_toll) C++17
100 / 100
 1589 ms 24364 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 3 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 5 ms 12968 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 5 ms 12968 KB Output is correct
5 Correct 6 ms 13144 KB Output is correct
6 Correct 6 ms 13148 KB Output is correct
7 Correct 149 ms 24036 KB Output is correct
8 Correct 160 ms 24184 KB Output is correct
9 Correct 154 ms 23756 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 5 ms 12968 KB Output is correct
5 Correct 6 ms 13144 KB Output is correct
6 Correct 6 ms 13148 KB Output is correct
7 Correct 149 ms 24036 KB Output is correct
8 Correct 160 ms 24184 KB Output is correct
9 Correct 154 ms 23756 KB Output is correct
10 Correct 1136 ms 23848 KB Output is correct
11 Correct 1589 ms 23732 KB Output is correct
12 Correct 1581 ms 24364 KB Output is correct