#include <bits/stdc++.h>
using namespace std;
#define SIZE_N 200005
#define SIZE_M 400005
#define INFL LLONG_MAX/3
using ll=long long;
struct edge{
ll a,b,c;
bool operator<(const edge p)const{
if(c!=p.c)return c<p.c;
if(a!=p.a)return a<p.a;
return b<p.b;
}
bool operator>(const edge p)const{
if(c!=p.c)return c>p.c;
if(a!=p.a)return a>p.a;
return b>p.b;
}
};
struct UnionFind{
int par[SIZE_N];
void init(int n){
for(int i=0;i<n;i++){
par[i]=i;
}
}
int find(int x){
if(x==par[x])return x;
return par[x]=find(par[x]);
}
bool same(int x,int y){
return find(x)==find(y);
}
void unit(int x,int y){
x=find(x);
y=find(y);
if(x==y)return;
par[x]=y;
}
}uf;
ll n,m,q,s[SIZE_N],ans,ma,sum,d[SIZE_N],miv;
edge e[SIZE_M];
pair<ll,ll>mi=make_pair(INFL,-1);
vector<ll>ansrev;
bool con[SIZE_N];
vector<edge>g;
struct all_edge{
ll a,b,par,c;
bool operator<(const all_edge p)const{
if(c!=p.c)return c<p.c;
if(par!=p.par)par<p.par;
if(a!=p.a)return a<p.a;
return b<p.b;
}
bool operator>(const all_edge p)const{
if(c!=p.c)return c>p.c;
if(par!=p.par)par>p.par;
if(a!=p.a)return a>p.a;
return b>p.b;
}
};
ll pa[SIZE_N],toe[SIZE_N];
priority_queue<edge,vector<edge>,greater<edge>>have[SIZE_N];
priority_queue<all_edge,vector<all_edge>,greater<all_edge>>all;
ll find_pa(ll x){
if(x==pa[x])return x;
return pa[x]=find_pa(pa[x]);
}
int main(void){
scanf("%lld%lld%lld",&n,&m,&q);
for(int i=0;i<n;i++){
scanf("%lld",&s[i]);
ma=max(ma,s[i]);
mi=min(mi,make_pair(s[i],ll(i)));
sum+=s[i];
}
miv=mi.second;
for(int i=0;i<m;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
a--,b--;
if(a>b)swap(a,b);
e[i]=edge{a,b,s[a]+s[b]};
}
sort(e,e+m);
uf.init(n);
for(int i=0;i<m;i++){
ll a=e[i].a,b=e[i].b;
if(!uf.same(a,b)){
ans+=e[i].c;
uf.unit(a,b);
g.push_back(e[i]);
}
}
for(auto i:g){
if(i.a==miv)con[i.b]=true;
else if(i.b==miv)con[i.a]=true;
else{
have[i.a].push(edge{i.a,i.b,i.c});
have[i.b].push(edge{i.b,i.a,i.c});
}
}
for(int i=0;i<n;i++){
pa[i]=i;
toe[i]=i;
if(!con[i]&&!have[i].empty()){
edge x=have[i].top();
all.push(all_edge{x.a,x.b,x.a,-(s[miv]+s[x.a])+x.c});
}
}
ll start=(n-2)*mi.first+sum;
ansrev.push_back(start);
while(!all.empty()){
all_edge al=all.top();
ll a=all.top().a,b=all.top().b,c=all.top().c,d=all.top().par;
all.pop();
if(find_pa(a)==find_pa(b)||find_pa(a)!=d)continue;
start+=c;
ansrev.push_back(start);
a=find_pa(a);
b=find_pa(b);
ll x=toe[a],y=toe[b];
if(have[x].size()>have[y].size())swap(x,y);
while(!have[x].empty()){
have[y].push(have[x].top());
have[x].pop();
}
pa[a]=b;
if(con[b])continue;
toe[b]=y;
while(!have[y].empty()&&find_pa(have[y].top().a)==find_pa(have[y].top().b))have[y].pop();
if(!have[y].empty())all.push(all_edge{have[y].top().a,have[y].top().b,b,-(s[miv]+s[b])+have[y].top().c});
}
reverse(ansrev.begin(),ansrev.end());
for(int i=0;i<=q;i++){
if(ansrev.size()<=i)printf("%lld\n",ansrev.back()-sum+ma);
else printf("%lld\n",ansrev[i]-sum+ma);
}
}
Compilation message
guard.cpp: In member function 'bool all_edge::operator<(all_edge) const':
guard.cpp:57:26: warning: statement has no effect [-Wunused-value]
57 | if(par!=p.par)par<p.par;
| ~~~^~~~~~
guard.cpp: In member function 'bool all_edge::operator>(all_edge) const':
guard.cpp:63:26: warning: statement has no effect [-Wunused-value]
63 | if(par!=p.par)par>p.par;
| ~~~^~~~~~
guard.cpp: In function 'int main()':
guard.cpp:123:18: warning: variable 'al' set but not used [-Wunused-but-set-variable]
123 | all_edge al=all.top();
| ^~
guard.cpp:145:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
145 | if(ansrev.size()<=i)printf("%lld\n",ansrev.back()-sum+ma);
| ~~~~~~~~~~~~~^~~
guard.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%lld%lld%lld",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%lld",&s[i]);
| ~~~~~^~~~~~~~~~~~~~
guard.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%lld%lld",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| # |
Verdict |
Execution time |
Memory |
Grader output |
