#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];
priority_queue<pair<int, int>> ed[N];
set<pair<int, int>> pos;
set<pair<int, int>>::iterator it;
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);
fau[b] = a;
}
void A(int v)
{
Find(v);
while((int)ed[v].size() > 0 && fau[v] == Find(ed[v].top().nd))
ed[v].pop();
if((int)ed[v].size() == 0) return;
pos.insert(pair{-ed[v].top().st - bst[v], v});
}
void R(int v)
{
if((int)ed[v].size() == 0) return;
pos.erase(pair{-ed[v].top().st - bst[v], v});
}
void Union2(int a, int b)
{
a = Find(a); b = Find(b);
R(a); R(b);
if((int)ed[a].size() < (int)ed[b].size()) swap(a, b);
fau[b] = a;
bst[a] = min(bst[a], bst[b]);
while((int)ed[b].size() > 0)
{
ed[a].push(ed[b].top());
ed[b].pop();
}
A(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);
for(int i = 1; i <= m; ++i)
{
if(Find(e[i].nd.st) == Find(e[i].nd.nd)) continue;
Union(e[i].nd.st, e[i].nd.nd);
ed[e[i].nd.st].push(pair{-e[i].st, e[i].nd.nd});
ed[e[i].nd.nd].push(pair{-e[i].st, e[i].nd.st});
}
for(int i = 1; i <= n; ++i)
{fau[i] = i; bst[i] = tab[i];}
for(int i = 1; i <= n; ++i)
A(i);
answer[n - 1] = ans;
//cout << "S: " << ans << "\n";
for(int l = 1; l < n; ++l)
{
ans -= mi; it = pos.begin();
ans += (*it).st;
int a = (*it).nd;
//cout << "L: " << l << " " << a << " " << ed[a].top().nd << " " << (*it).st << " | " << ans << '\n';
Union2(a, ed[a].top().nd);
answer[n - 1 - l] = ans;
}
int j = -1;
for(int i = 0; i <= q; ++i)
{
if(j < n - 1) ++j;
cout << answer[j] << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//int t; cin >> t;
//while(t--)
Solve();
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... |