Submission #1208000

#TimeUsernameProblemLanguageResultExecution timeMemory
1208000PenguinsAreCuteSecurity Guard (JOI23_guard)C++17
50 / 100
211 ms8260 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; } }; 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}); } sort(edge.begin(),edge.end()); long long ans = 0; ufds u(n); for(int i=0;i<m;i++) if(u.unite(get<1>(edge[i]),get<2>(edge[i]))) ans += get<0>(edge[i]); for(int i=0;i<n;i++) ans -= s[i]; ans += *max_element(s,s+n); cout << ans; }
#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...