Submission #1143358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143358		monkey133	Security Guard (JOI23_guard)	C++20	100 / 100	209 ms	30060 KiB

guard

#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[500005],Y[500005],Z[500005],W[500005];

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;
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 13 / 13
• Subtask 5: 8 / 8
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24