제출 #937063

#제출 시각아이디문제언어결과실행 시간메모리
937063PacybwoahSecurity Guard (JOI23_guard)C++17
100 / 100
824 ms88620 KiB
#include<iostream> #include<algorithm> #include<vector> #include<utility> #include<queue> #include<set> #include<cassert> using namespace std; typedef long long ll; vector<int> dsu,rep,sz; int query(int x){ if(x==dsu[x]) return x; dsu[x]=query(dsu[x]); return dsu[x]; } void unite(int a,int b){ a=query(a); b=query(b); if(a==b) return; if(sz[a]<sz[b]) swap(a,b); dsu[b]=a; sz[a]+=sz[b]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m,q; cin>>n>>m>>q; vector<ll> s(n+1); for(int i=1;i<=n;i++) cin>>s[i]; int a,b; vector<pair<int,int> > ori,edges; for(int i=0;i<m;i++){ cin>>a>>b; ori.push_back(make_pair(a,b)); } sort(ori.begin(),ori.end(),[&](pair<int,int> a,pair<int,int> b){return s[a.first]+s[a.second]<s[b.first]+s[b.second];}); vector<priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > > pq(n+1); set<pair<ll,int> > finpq; vector<bool> vis(n-1); dsu.resize(n+1); rep.resize(n+1); sz.resize(n+1); int minpos; vector<bool> used(n+1); auto build=[&](){ for(int i=1;i<=n;i++){ dsu[i]=i; sz[i]=1; rep[i]=i; } if(!edges.empty()){ for(int i=0;i<=m;i++){ auto &[u,v]=edges[i]; pq[u].push(make_pair(s[u]+s[v],i)); pq[v].push(make_pair(s[u]+s[v],i)); } for(int i=1;i<=n;i++){ if(i==minpos||pq[i].empty()||used[i]) continue; finpq.insert(make_pair(pq[i].top().first-s[rep[i]],i)); //cout<<i<<"\n\n"; } } }; build(); for(auto &[u,v]:ori){ if(query(u)!=query(v)){ unite(u,v); edges.push_back(make_pair(u,v)); } } vector<ll> ans(n); ll smin=2e9,smax=0; for(int i=1;i<=n;i++){ if(s[i]<smin){ smin=s[i]; minpos=i; } smax=max(smax,s[i]); ans[n-1]-=s[i]; } ans[n-1]+=smax; for(int i=1;i<=n;i++){ if(i==minpos) continue; ans[n-1]+=smin+s[i]; } vector<pair<int,int> >().swap(ori); m=n-2; used[minpos]=1; for(auto [u,v]:edges){ if(u==minpos||v==minpos){ ans[m--]=ans[n-1]; used[u]=1; used[v]=1; } else{ ori.push_back(make_pair(u,v)); } } edges=ori; build(); for(int i=m;i>=0;i--){ auto [sum,node]=*finpq.begin(); finpq.erase(finpq.begin()); used[rep[node]]=1; ans[i]=ans[i+1]+sum-smin; //cout<<pq[8].size()<<" "<<sum<<"\n"; while(vis[pq[node].top().second]) pq[node].pop(); auto [w,eid]=pq[node].top(); vis[eid]=1; //cout<<eid<<"\n"; auto [u,v]=edges[eid]; //cout<<node<<" "<<eid<<"\n"; if(query(u)!=node) swap(u,v); u=query(u); v=query(v); if(finpq.count(make_pair(pq[v].top().first-s[rep[v]],v))) finpq.erase(make_pair(pq[v].top().first-s[rep[v]],v)); a=u; b=v; if(pq[a].size()<pq[b].size()) swap(a,b); //cout<<pq[a].size()<<" "<<pq[b].size()<<"\n"; dsu[b]=a; //cout<<minpos<<" "<<u<<" "<<v<<"\n"; while(!pq[b].empty()){ if(vis[pq[b].top().second]){ pq[b].pop(); } else{ pq[a].push(pq[b].top()); pq[b].pop(); } //cout<<b<<" "<<pq[b].size()<<"\n"; } rep[a]=rep[v]; if(!used[rep[a]]){ while(!pq[a].empty()){ if(vis[pq[a].top().second]){ pq[a].pop(); } else{ finpq.insert(make_pair(pq[a].top().first-s[rep[a]],a)); //cout<<pq[a].top().first-s[rep[a]]<<" "<<a<<"\n\n"; break; } } } } for(int i=0;i<=q;i++){ if(i>=n) cout<<ans[n-1]<<"\n"; else cout<<ans[i]<<"\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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...