This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
_ _ __ _ _ _ _ _ _
|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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |