Submission #943513

#TimeUsernameProblemLanguageResultExecution timeMemory
943513alextodoranSecurity Guard (JOI23_guard)C++17
0 / 100
4085 ms313708 KiB
/** _ _ __ _ _ _ _ _ _ |a ||t ||o d | |o | | __ _| | _ | __| _ | | __ |/_ | __ /__\ / _\| **/ #include <bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int N_MAX = 200000; const int M_MAX = 400000; int N, M, Q; int S[N_MAX + 2]; int edge_u[M_MAX + 2], edge_v[M_MAX + 2]; int order[M_MAX + 2]; int leader[N_MAX + 2]; int find_leader (int u) { return (leader[u] == 0 ? u : leader[u] = find_leader(leader[u])); } bool join (int u, int v) { u = find_leader(u); v = find_leader(v); if (u != v) { leader[u] = v; return true; } return false; } vector <int> adj[N_MAX + 2]; int root; ll cost; void init () { int mx = 0; for (int u = 1; u <= N; u++) { cost -= S[u]; mx = max(mx, S[u]); } cost += mx; root = 1; for (int u = 2; u <= N; u++) { if (S[u] < S[root]) { root = u; } } for (int u = 1; u <= N; u++) { if (u != root) { cost += S[u] + S[root]; } } } ll answer[N_MAX + 2]; set <tuple <int, int, int>> st; int min_comp[N_MAX + 2]; vector <int> comp[N_MAX + 2]; signed main () { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> M >> Q; for (int u = 1; u <= N; u++) { cin >> S[u]; } for (int i = 1; i <= M; i++) { cin >> edge_u[i] >> edge_v[i]; } iota(order + 1, order + M + 1, 1); sort(order + 1, order + M + 1, [&] (const int &i, const int &j) { return S[edge_u[i]] + S[edge_v[i]] < S[edge_u[j]] + S[edge_v[j]]; }); for (int _ = 1; _ <= M; _++) { int i = order[_]; if (join(edge_u[i], edge_v[i]) == true) { adj[edge_u[i]].push_back(edge_v[i]); adj[edge_v[i]].push_back(edge_u[i]); } } init(); answer[N - 1] = cost; fill(leader + 1, leader + N + 1, 0); for (int u = 1; u <= N; u++) { min_comp[u] = S[u]; comp[u] = {u}; } for (int u = 1; u <= N; u++) { for (int v : adj[u]) { if (u < v) { st.insert(make_tuple(S[u] + S[v] - max(S[u], S[v]), u, v)); } } } for (int k = N - 2; k >= 0; k--) { int delta, u, v; tie(delta, u, v) = *st.begin(); st.erase(st.begin()); cost += delta; cost -= S[root]; answer[k] = cost; u = find_leader(u); v = find_leader(v); if (min_comp[u] < min_comp[v]) { swap(u, v); } while (comp[u].empty() == false) { int x = comp[u].back(); comp[u].pop_back(); comp[v].push_back(x); for (int y : adj[x]) { set <tuple <int, int, int>> :: iterator it = st.find(make_tuple(S[x] + S[y] - max(min_comp[x], min_comp[y]), min(x, y), max(x, y))); if (it != st.end()) { st.erase(it); st.insert(make_tuple(S[x] + S[y] - max(min_comp[v], min_comp[y]), min(x, y), max(x, y))); } } min_comp[x] = min_comp[v]; } leader[u] = v; } for (int i = 0; i <= Q; i++) { cout << answer[i] << "\n"; } 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...