| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1143355 | monkey133 | Security Guard (JOI23_guard) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define f first #define s second #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define all(x)(x).begin(),(x).end() using namespace std;mt19937_64 Sa7B(chrono::steady_clock::now().time_since_epoch().count());typedef long long ll;typedef long double ld;typedef pair<ld,ll>pdl;typedef pair<ll,ll>pll;typedef pair<ll,pll>plll;mt19937 Go9Z(chrono::steady_clock::now().time_since_epoch().count());ll X[100005],Y[100005],Z[100005],W[100005];ll F(ll u){return X[u]==u?u:X[u]=F(X[u]);}void U(ll a,ll b){a=F(a);b=F(b);if(a!=b)X[b]=a;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);ll n,m,q,mn,mx;cin>>n>>m>>q;for(ll i=1;i<=n;i++)cin>>Z[i];mn=*min_element(Z+1,Z+n+1);mx=*max_element(Z+1,Z+n+1);vector<plll>ed;for(ll i=0;i<m;i++){ll A,B;cin>>A>>B;ed.pb(mp(Z[A]+Z[B],pll(A,B)));}sort(all(ed));for(ll i=1;i<=n;i++)X[i]=i;priority_queue<plll,vector<plll>,greater<plll>>pq;for(auto&e:ed){if(F(e.s.f)==F(e.s.s))continue;ll r=F(e.s.f),s=F(e.s.s);if(Z[r]>Z[s])swap(r,s);U(r,s);pq.push(mp(Z[r]-mn,e.s));}for(ll i=1;i<=n;i++){X[i]=i;Y[i]=Z[i]+mn;}W[n-1]=mx+(n-2)*mn;for(ll i=n-2;i>=0;){auto t=pq.top();pq.pop();ll a=t.s.f,b=t.s.s;if(F(a)==F(b))continue;ll cost=Z[a]+Z[b]-max(Y[F(a)],Y[F(b)]);if(cost!=t.f){pq.push(mp(cost,t.s));continue;}if(Y[F(a)]>Y[F(b)])swap(a,b);U(a,b);W[i]=cost+W[i+1];i--;}for(ll i=0;i<=q;i++)cout<<W[min(i,n-1)]<<"\n";return 0;}