Submission #1208026

#TimeUsernameProblemLanguageResultExecution timeMemory
1208026PenguinsAreCuteSecurity Guard (JOI23_guard)C++17
8 / 100
4091 ms9012 KiB
#include <bits/stdc++.h> using namespace std; struct ufds { int n; vector<int> par; ufds(int _n): n(_n), par(_n,-1) {} int onion(int x) {return (par[x]<0?x:par[x]=onion(par[x]));} bool unite(int x, int y) { x=onion(x), y=onion(y); if(x==y) return 0; if(par[x]<par[y]) swap(x,y); par[y]+=par[x]; par[x]=y; return 1; } }; long long mst(int n, vector<tuple<int,int,int>> edge) { sort(edge.begin(),edge.end()); long long ans = 0; ufds dsu(n); for(auto [w, u, v]: edge) if(dsu.unite(u,v)) ans += w; return ans; } int main() { int n, m, q; cin >> n >> m >> q; int s[n], d[n]; for(int i=0;i<n;i++) cin >> s[i]; memset(d,0,sizeof(d)); vector<tuple<int,int,int>> edge; for(int i=0;i<m;i++) { int a, b; cin >> a >> b; a--; b--; edge.push_back({s[a]+s[b],a,b}); } int small = min_element(s,s+n)-s; long long ans[n]; memset(ans,1,sizeof(ans)); ans[0] = mst(n,edge); for(int i=1;i<n;i++) { pair<long long,int> bst = {1e18,-1}; for(int j=0;j<n;j++) { edge.push_back({s[small]+s[j],small,j}); bst = min(bst,{mst(n,edge),j}); edge.pop_back(); } edge.push_back({s[small]+s[bst.second],small,bst.second}); ans[i] = bst.first; } long long delta = 0; for(int i=0;i<n;i++) delta -= s[i]; delta += *max_element(s,s+n); for(int i=0;i<=q;i++) cout << ans[min(i,n-1)] + delta << "\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...