#include <bits/stdc++.h>
using namespace std;
struct ufds {
int n;
vector<int> par;
ufds(int _n): n(_n), par(_n,-1) {}
int onion(int x) {return (par[x]<0?x:par[x]=onion(par[x]));}
bool unite(int x, int y) {
x=onion(x), y=onion(y);
if(x==y)
return 0;
if(par[x]<par[y])
swap(x,y);
par[y]+=par[x];
par[x]=y;
return 1;
}
};
struct tree {
vector<int> x, d, w, s;
int n;
tree(int _n, vector<int> _s): n(_n), x(_n,0), d(_n,0), w(_n,0), s(_s) {}
void t(int a, int b) {
x[a] ^= b;
x[b] ^= a;
d[a]++;
d[b]++;
w[a] ^= (s[a] + s[b]);
w[b] ^= (s[a] + s[b]);
}
tuple<int,int,int> orz() {
int ord[n], cnt = 0;
int k = min_element(s.begin(),s.end())-s.begin();
d[k] = 0;
for(int i=0;i<n;i++)
for(int j=i;d[j]==1;j=x[j]) {
d[j]--;
d[x[j]]--;
x[x[j]] ^= j;
w[x[j]] ^= w[j];
ord[cnt++] = j;
}
pair<int,int> maxEdge[n];
memset(maxEdge,-128,sizeof(maxEdge));
while(cnt--)
maxEdge[ord[cnt]] = max(maxEdge[x[ord[cnt]]],{w[ord[cnt]],ord[cnt]});
tuple<int,int,int> bst = {1,0,0};
for(int i=0;i<n;i++)
if(i!=k)
bst = min(bst,{s[i] - maxEdge[i].first, i, maxEdge[i].second});
get<0>(bst) += *min_element(s.begin(),s.end());
return bst;
}
};
int main() {
int n, m, q;
cin >> n >> m >> q;
int d[n];
vector<int> s(n);
for(int i=0;i<n;i++)
cin >> s[i];
memset(d,0,sizeof(d));
vector<tuple<int,int,int>> edge;
for(int i=0;i<m;i++) {
int a, b;
cin >> a >> b;
a--; b--;
edge.push_back({s[a]+s[b],a,b});
}
vector<pair<int,int>> real;
int small = min_element(s.begin(),s.end())-s.begin();
long long ans[n];
memset(ans,1,sizeof(ans));
ans[0] = 0;
sort(edge.begin(),edge.end());
ufds dsu(n);
for(auto [w, u, v]: edge)
if(dsu.unite(u,v)) {
ans[0] += w;
real.push_back({u,v});
}
for(int i=1;i<min(n,q+1);i++) {
ans[i] = ans[i-1];
tree tyx(n,s);
for(auto [y, x]: real)
tyx.t(y,x);
auto res = tyx.orz();
ans[i] += get<0>(res);
int a = get<2>(res);
int b = tyx.x[a];
auto it = find(real.begin(),real.end(),make_pair(a,b));
if(it != real.end())
real.erase(it);
it = find(real.begin(),real.end(),make_pair(b,a));
if(it != real.end())
real.erase(it);
real.push_back(make_pair(small,get<1>(res)));
}
long long delta = 0;
for(int i=0;i<n;i++)
delta -= s[i];
delta += *max_element(s.begin(),s.end());
for(int i=0;i<=q;i++)
cout << ans[min(i,n-1)] + delta << "\n";
}
# | 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... |