Submission #1216270

#TimeUsernameProblemLanguageResultExecution timeMemory
1216270jerzykSecurity Guard (JOI23_guard)C++20
50 / 100
427 ms62760 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], bst[N]; pair<int, pair<int, int>> e[N]; priority_queue<pair<int, int>> ed[N]; set<pair<int, int>> pos; set<pair<int, int>>::iterator it; int tab[N]; ll ans = 0LL; ll answer[N]; int Find(int v) { if(fau[v] == v) return v; return (fau[v] = Find(fau[v])); } void Union(int a, int b) { a = Find(a); b = Find(b); fau[b] = a; } void A(int v) { Find(v); while((int)ed[v].size() > 0 && fau[v] == Find(ed[v].top().nd)) ed[v].pop(); if((int)ed[v].size() == 0) return; pos.insert(pair{-ed[v].top().st - bst[v], v}); } void R(int v) { if((int)ed[v].size() == 0) return; pos.erase(pair{-ed[v].top().st - bst[v], v}); } void Union2(int a, int b) { a = Find(a); b = Find(b); R(a); R(b); if((int)ed[a].size() < (int)ed[b].size()) swap(a, b); fau[b] = a; bst[a] = min(bst[a], bst[b]); while((int)ed[b].size() > 0) { ed[a].push(ed[b].top()); ed[b].pop(); } A(a); } void Solve() { int n, m, a, b, q, ma = 0, mi = II; cin >> n >> m >> q; for(int i = 1; i <= n; ++i) { fau[i] = i; cin >> tab[i]; bst[i] = tab[i]; ma = max(ma, tab[i]); mi = min(mi, tab[i]); } ans = ma; ans += (ll)(n - 2) * (ll)mi; 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; Union(e[i].nd.st, e[i].nd.nd); ed[e[i].nd.st].push(pair{-e[i].st, e[i].nd.nd}); ed[e[i].nd.nd].push(pair{-e[i].st, e[i].nd.st}); } for(int i = 1; i <= n; ++i) {fau[i] = i; bst[i] = tab[i];} for(int i = 1; i <= n; ++i) A(i); answer[n - 1] = ans; //cout << "S: " << ans << "\n"; for(int l = 1; l < n; ++l) { ans -= mi; it = pos.begin(); ans += (*it).st; int a = (*it).nd; //cout << "L: " << l << " " << a << " " << ed[a].top().nd << " " << (*it).st << " | " << ans << '\n'; Union2(a, ed[a].top().nd); answer[n - 1 - l] = ans; } int j = -1; for(int i = 0; i <= q; ++i) { if(j <= n - 1) ++j; cout << answer[i] << "\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...