Submission #1110156

#TimeUsernameProblemLanguageResultExecution timeMemory
1110156vjudge1Toll (APIO13_toll)C++17
100 / 100
1526 ms32420 KiB
#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'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...