제출 #1216131

#제출 시각아이디문제언어결과실행 시간메모리
1216131jerzykSecurity Guard (JOI23_guard)C++20
50 / 100
112 ms21392 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]; vector<int> ed[N]; 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); ans -= bst[a] + bst[b]; bst[a] = min(bst[a], bst[b]); ans += bst[a]; fau[b] = 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); int cnt = 0; answer[n - 1] = ans; for(int i = 1; i <= m; ++i) { if(Find(e[i].nd.st) == Find(e[i].nd.nd)) continue; ans += e[i].st; ans -= mi; Union(e[i].nd.st, e[i].nd.nd); ++cnt; answer[n - 1 - cnt] = 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...