Submission #1215958

#TimeUsernameProblemLanguageResultExecution timeMemory
1215958jerzykSecurity Guard (JOI23_guard)C++20
50 / 100
102 ms19100 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1'000'000'000'000'000'000LL; const int II = 2'000'000'000; const ll M = 1'000'000'007LL; const int N = 1<<19; int fau[N]; pair<int, pair<int, int>> e[N]; vector<int> ed[N]; int tab[N]; ll ans = 0LL; int Find(int v) { if(fau[v] == v) return v; return (fau[v] = Find(fau[v])); } void Union(int a, int b) { fau[Find(b)] = Find(a); } void Solve() { int n, m, a, b, q, ma = 0; cin >> n >> m >> q; for(int i = 1; i <= n; ++i) { fau[i] = i; cin >> tab[i]; ans -= tab[i]; ma = max(ma, tab[i]); } ans += ma; for(int i = 1; i <= m; ++i) { cin >> a >> b; e[i] = pair{tab[a] + tab[b], pair{a, b}}; } sort(e + 1, e + 1 + m); for(int i = 1; i <= m; ++i) { if(Find(e[i].nd.st) == Find(e[i].nd.nd)) continue; ans += e[i].st; Union(e[i].nd.st, e[i].nd.nd); } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); //int t; cin >> t; //while(t--) Solve(); return 0; }
#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...