Submission #970809

#TimeUsernameProblemLanguageResultExecution timeMemory
970809thinknoexitSecurity Guard (JOI23_guard)C++17
100 / 100
175 ms30972 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; const int N = 200200; int a[N], p[N]; struct Edge { int u, v; ll w; bool operator < (const Edge& o) const { return w > o.w; } }; vector<Edge> e; priority_queue<Edge> pq; int fr(int i) { return p[i] == i ? i : p[i] = fr(p[i]); } ll res[N], cost[N]; int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, m, q; cin >> n >> m >> q; for (int i = 1;i <= n;i++) cin >> a[i]; int mn = *min_element(a + 1, a + 1 + n); int mx = *max_element(a + 1, a + 1 + n); res[n - 1] = mx + 1ll * (n - 2) * mn; for (int i = 1;i <= n;i++) p[i] = i; while (m--) { int u, v; cin >> u >> v; e.push_back({ u, v, a[u] + a[v] }); } int idx = 0; sort(e.rbegin(), e.rend()); for (auto& x : e) { int u = x.u, v = x.v; int pu = fr(u), pv = fr(v); if (pu == pv) continue; p[pu] = pv; if (a[u] < a[v]) swap(u, v); pq.push({ u, v, a[v] - mn }); } for (int i = 1;i <= n;i++) p[i] = i, cost[i] = a[i] + mn; int now = n - 2; while (now >= 0) { auto x = pq.top(); pq.pop(); int u = x.u, v = x.v; if (fr(u) == fr(v)) continue; ll w = x.w; ll w2 = a[u] + a[v] - max(cost[fr(u)], cost[fr(v)]); if (w != w2) { pq.push({ u, v, w2 }); continue; } if (cost[fr(u)] < cost[fr(v)]) swap(u, v); p[fr(u)] = fr(v); res[now] = res[now + 1] + w; now--; } for (int i = 0;i <= q;i++) { cout << res[min(i, n - 1)] << '\n'; } return 0; } /* 2 3 1 2 3 6 8 9 6 9 9 10 1 4 7 8 2 5 */

Compilation message (stderr)

guard.cpp: In function 'int main()':
guard.cpp:33:9: warning: unused variable 'idx' [-Wunused-variable]
   33 |     int idx = 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...