This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, mn, mx;
ll a[200200];
pair<int, int> E[400400];
ll ans[200200];
priority_queue<array<ll, 4>, vector<array<ll, 4>>, greater<array<ll, 4>>> pq;
struct DSU{
int path[200200], valid[200200], n;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq2[200200];
void init(int N){
n = N;
for (int i=1;i<=n;i++){
path[i] = i;
valid[i] = 1;
}
}
void reset(int x){valid[x] = 0;}
void push(int x, int y){
pq2[x].emplace(a[x]+a[y], y);
pq2[y].emplace(a[x]+a[y], x);
}
void init2(){
for (int i=1;i<=n;i++) if (valid[i] && !pq2[i].empty()){
auto [cst, v] = pq2[i].top();
pq.push({cst - a[i] - a[mn], cst, v, i});
}
}
int find(int s){
if (path[s]==s) return s;
return path[s] = find(path[s]);
}
void refresh(int s, int p = 0){
s = find(s);
if (!valid[s]) return;
int flag = p;
while(!pq2[s].empty() && find(pq2[s].top().second)==s){
flag = 1;
pq2[s].pop();
}
if (!flag) return;
if (!pq2[s].empty()){
auto [cst, nxt] = pq2[s].top();
pq.push({cst - a[s] - a[mn], cst, nxt, s});
}
}
void merge(int s, int v){
s = find(s), v = find(v);
assert(s!=v);
assert(valid[v]);
path[v] = s;
if (!valid[s]) return;
if (pq2[s].size() < pq2[v].size()) swap(pq2[s], pq2[v]);
while(!pq2[v].empty()){
pq2[s].push(pq2[v].top()); pq2[v].pop();
}
refresh(s, 1);
}
}dsu;
bool valid(const array<ll, 4> &p){
if (dsu.find(p[2]) == dsu.find(p[3])) return 0;
return p[1] - a[mn] - a[dsu.find(p[3])] == p[0];
}
int main(){
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for (int i=1;i<=n;i++) scanf("%lld", a+i);
for (int i=1;i<=m;i++){
int x, y;
scanf("%d %d", &x, &y);
E[i] = {x, y};
}
mn = min_element(a+1, a+n+1) - a;
mx = max_element(a+1, a+n+1) - a;
dsu.init(n);
int sz = n-1;
for (int i=1;i<=m;i++){
if (E[i].first==mn || E[i].second==mn){
if (E[i].second==mn) swap(E[i].first, E[i].second);
dsu.reset(E[i].second);
sz--;
}
else{
dsu.push(E[i].first, E[i].second);
}
}
dsu.init2();
for (int i=1;i<=n;i++) ans[sz] += a[i];
ans[sz] += a[mn] * (n-2);
for (int i=sz-1;i>=0;i--){
while(!pq.empty()){
if (!valid(pq.top())){
int tmp = pq.top()[3];
pq.pop();
dsu.refresh(tmp);
}
else break;
}
assert(!pq.empty());
auto [cst, _, u, v] = pq.top();
dsu.merge(u, v);
ans[i] = ans[i+1] + cst;
}
ll ofs = a[mx];
for (int i=1;i<=n;i++) ofs -= a[i];
for (int i=0;i<=q;i++) printf("%lld\n", ans[min(i, sz)] + ofs);
}
Compilation message (stderr)
guard.cpp: In function 'int main()':
guard.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:89:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | for (int i=1;i<=n;i++) scanf("%lld", a+i);
| ~~~~~^~~~~~~~~~~~~
guard.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
# | 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... |