oj.uz

Submission #952509

# Submission time Handle Problem Language Result Execution time Memory
952509 2024-03-24T07:24:25 Z ttamx Security Guard (JOI23_guard) C++17
12 / 100
 304 ms 40228 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;

using ll = long long;
using T = tuple<ll,int,int>;
using U = tuple<ll,int,int,int>;

int n,m,q;
int s[N],deg[N];
int rt;
ll cur;
vector<T> edge;
priority_queue<T,vector<T>,greater<T>> comp[N];
priority_queue<U,vector<U>,greater<U>> pq;
bool good[N];
vector<ll> ans;

struct DSU{
    int p[N];
    void init(){
        for(int i=1;i<=n;i++)p[i]=i;
    }
    int fp(int u){
        return p[u]=u==p[u]?u:fp(p[u]);
    }
    bool uni(int u,int v){
        u=fp(u),v=fp(v);
        return u!=v?p[u]=v,true:false;
    }
}dsu;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++){
        cin >> s[i];
    }
    rt=min_element(s+1,s+n+1)-s;
    cur+=(n-2)*s[rt]+*max_element(s+1,s+n+1);
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        edge.emplace_back(s[u]+s[v],u,v);
    }
    sort(edge.begin(),edge.end());
    dsu.init();
    for(auto [w,u,v]:edge)if(dsu.uni(u,v)){
        if(u==rt||v==rt)good[u]=good[v]=true;
        else{
            comp[u].emplace(w,u,v);
            comp[v].emplace(w,v,u);
        }
    }
    good[rt]=false;
    dsu.init();
    for(int i=1;i<=n;i++)if(!good[i]&&!comp[i].empty()){
        auto [w,u,v]=comp[i].top();
        pq.emplace(w-(s[rt]+s[u]),u,v,i);
    }
    ans.emplace_back(cur);
    while(!pq.empty()){
        auto [w,u,v,p]=pq.top();
        pq.pop();
        u=dsu.fp(u),v=dsu.fp(v);
        if(u==v||u!=p)continue;
        cur+=w;
        ans.emplace_back(cur);
        if(comp[u].size()>comp[v].size())swap(comp[u],comp[v]);
        dsu.p[u]=v;
        while(!comp[u].empty()){
            comp[v].emplace(comp[u].top());
            comp[u].pop();
        }
        if(good[v])continue;
        while(!comp[v].empty()){
            auto [c,a,b]=comp[v].top();
            if(dsu.fp(a)!=dsu.fp(b))break;
            comp[v].pop();
        }
        if(!comp[v].empty()){
            auto [c,a,b]=comp[v].top();
            pq.emplace(c-(s[rt]+s[v]),a,b,v);
        }
    }
    reverse(ans.begin(),ans.end());
    for(int i=0;i<=q;i++)cout << ans[min(i,(int)ans.size()-1)] << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 100 ms 39028 KB Output is correct
3 Correct 94 ms 39996 KB Output is correct
4 Correct 184 ms 40120 KB Output is correct
5 Correct 164 ms 38824 KB Output is correct
6 Correct 171 ms 38936 KB Output is correct
7 Correct 162 ms 40228 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 100 ms 39028 KB Output is correct
3 Correct 94 ms 39996 KB Output is correct
4 Correct 184 ms 40120 KB Output is correct
5 Correct 164 ms 38824 KB Output is correct
6 Correct 171 ms 38936 KB Output is correct
7 Correct 162 ms 40228 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 304 ms 36956 KB Output is correct
11 Incorrect 102 ms 39100 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 100 ms 39028 KB Output is correct
3 Correct 94 ms 39996 KB Output is correct
4 Correct 184 ms 40120 KB Output is correct
5 Correct 164 ms 38824 KB Output is correct
6 Correct 171 ms 38936 KB Output is correct
7 Correct 162 ms 40228 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 304 ms 36956 KB Output is correct
11 Incorrect 102 ms 39100 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 100 ms 39028 KB Output is correct
3 Correct 94 ms 39996 KB Output is correct
4 Correct 184 ms 40120 KB Output is correct
5 Correct 164 ms 38824 KB Output is correct
6 Correct 171 ms 38936 KB Output is correct
7 Correct 162 ms 40228 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 304 ms 36956 KB Output is correct
11 Incorrect 102 ms 39100 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 13 ms 10840 KB Output is correct
9 Correct 13 ms 10840 KB Output is correct
10 Correct 13 ms 10584 KB Output is correct
11 Incorrect 19 ms 11044 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 13 ms 10840 KB Output is correct
9 Correct 13 ms 10840 KB Output is correct
10 Correct 13 ms 10584 KB Output is correct
11 Incorrect 19 ms 11044 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 100 ms 39028 KB Output is correct
3 Correct 94 ms 39996 KB Output is correct
4 Correct 184 ms 40120 KB Output is correct
5 Correct 164 ms 38824 KB Output is correct
6 Correct 171 ms 38936 KB Output is correct
7 Correct 162 ms 40228 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 304 ms 36956 KB Output is correct
11 Incorrect 102 ms 39100 KB Output isn't correct
12 Halted 0 ms 0 KB -