oj.uz

Submission #952503

# Submission time Handle Problem Language Result Execution time Memory
952503 2024-03-24T07:14:00 Z ttamx Security Guard (JOI23_guard) C++17
12 / 100
 280 ms 37232 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,ans[N];
vector<T> edge;
priority_queue<T,vector<T>,greater<T>> comp[N];
priority_queue<U,vector<U>,greater<U>> pq;

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)){
        comp[u].emplace(w,u,v);
        comp[v].emplace(w,v,u);
    }
    dsu.init();
    for(int i=1;i<=n;i++)if(!comp[i].empty()){
        auto [w,u,v]=comp[i].top();
        pq.emplace(w-(s[rt]+s[u]),u,v,i);
    }
    int cnt=n-1;
    ans[cnt]=cur;
    while(!pq.empty()&&cnt>=0){
        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[--cnt]=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();
        }
        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);
        }
    }
    assert(cnt==0);
    for(int i=0;i<=q;i++)cout << ans[min(i,n-1)] << "\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 126 ms 33228 KB Output is correct
3 Correct 124 ms 33204 KB Output is correct
4 Correct 168 ms 36536 KB Output is correct
5 Correct 166 ms 37232 KB Output is correct
6 Correct 161 ms 34732 KB Output is correct
7 Correct 167 ms 34740 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 1 ms 8540 KB Output is correct
2 Correct 126 ms 33228 KB Output is correct
3 Correct 124 ms 33204 KB Output is correct
4 Correct 168 ms 36536 KB Output is correct
5 Correct 166 ms 37232 KB Output is correct
6 Correct 161 ms 34732 KB Output is correct
7 Correct 167 ms 34740 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 280 ms 33968 KB Output is correct
11 Incorrect 134 ms 33200 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 126 ms 33228 KB Output is correct
3 Correct 124 ms 33204 KB Output is correct
4 Correct 168 ms 36536 KB Output is correct
5 Correct 166 ms 37232 KB Output is correct
6 Correct 161 ms 34732 KB Output is correct
7 Correct 167 ms 34740 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 280 ms 33968 KB Output is correct
11 Incorrect 134 ms 33200 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 126 ms 33228 KB Output is correct
3 Correct 124 ms 33204 KB Output is correct
4 Correct 168 ms 36536 KB Output is correct
5 Correct 166 ms 37232 KB Output is correct
6 Correct 161 ms 34732 KB Output is correct
7 Correct 167 ms 34740 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 280 ms 33968 KB Output is correct
11 Incorrect 134 ms 33200 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 8540 KB Output is correct
2 Correct 2 ms 8540 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 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 14 ms 10844 KB Output is correct
9 Correct 14 ms 10848 KB Output is correct
10 Correct 14 ms 10600 KB Output is correct
11 Incorrect 14 ms 10844 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 8540 KB Output is correct
2 Correct 2 ms 8540 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 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 14 ms 10844 KB Output is correct
9 Correct 14 ms 10848 KB Output is correct
10 Correct 14 ms 10600 KB Output is correct
11 Incorrect 14 ms 10844 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 126 ms 33228 KB Output is correct
3 Correct 124 ms 33204 KB Output is correct
4 Correct 168 ms 36536 KB Output is correct
5 Correct 166 ms 37232 KB Output is correct
6 Correct 161 ms 34732 KB Output is correct
7 Correct 167 ms 34740 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 280 ms 33968 KB Output is correct
11 Incorrect 134 ms 33200 KB Output isn't correct
12 Halted 0 ms 0 KB -