oj.uz

Submission #936986

# Submission time Handle Problem Language Result Execution time Memory
936986 2024-03-03T07:50:03 Z Pacybwoah Security Guard (JOI23_guard) C++17
0 / 100
 4000 ms 40524 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
vector<int> dsu,rep,sz;
int query(int x){
    if(x==dsu[x]) return x;
    dsu[x]=query(dsu[x]);
    return dsu[x];
}
void unite(int a,int b){
    a=query(a);
    b=query(b);
    if(a==b) return;
    if(sz[a]<sz[b]) swap(a,b);
    dsu[b]=a;
    sz[a]+=sz[b];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<ll> s(n+1);
    for(int i=1;i<=n;i++) cin>>s[i];
    int a,b;
    vector<pair<int,int> > ori,edges;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        ori.push_back(make_pair(a,b));
    }
    sort(ori.begin(),ori.end(),[&](pair<int,int> a,pair<int,int> b){return s[a.first]+s[a.second]<s[b.first]+s[b.second];});
    vector<priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > > pq(n+1);
    set<pair<ll,int> > finpq;
    vector<bool> vis(n-1);
    dsu.resize(n+1);
    rep.resize(n+1);
    sz.resize(n+1);
    int minpos;
    auto build=[&](){
        for(int i=1;i<=n;i++){
            dsu[i]=i;
            sz[i]=1;
            rep[i]=i;
        }
        if(!edges.empty()){
            for(int i=0;i<n-1;i++){
                auto &[u,v]=edges[i];
                pq[u].push(make_pair(s[u]+s[v],i));
                pq[v].push(make_pair(s[u]+s[v],i));
            }
            for(int i=1;i<=n;i++){
                if(i==minpos) continue;
                finpq.insert(make_pair(pq[i].top().first-s[rep[i]],i));
            }
        }
    }; 
    build();
    for(auto &[u,v]:ori){
        if(query(u)!=query(v)){
            unite(u,v);
            edges.push_back(make_pair(u,v));
        }
    }
    vector<ll> ans(n);
    ll smin=2e9,smax=0;
    for(int i=1;i<=n;i++){
        if(s[i]<smin){
            smin=s[i];
            minpos=i;
        }
        smax=max(smax,s[i]);
        ans[n-1]-=s[i];
    }
    ans[n-1]+=smax;
    for(int i=1;i<=n;i++){
        if(i==minpos) continue;
        ans[n-1]+=smin+s[i];
    }
    build();
    for(int i=n-2;i>=0;i--){
        auto [sum,node]=*finpq.begin();
        finpq.erase(finpq.begin());
        ans[i]=ans[i+1]+sum-smin;
        auto [w,eid]=pq[node].top();
        vis[eid]=1;
        auto [u,v]=edges[eid];
        if(query(u)!=node) swap(u,v);
        v=query(v);
        finpq.erase(make_pair(pq[v].top().first-s[rep[v]],v));
        a=u;
        b=v;
        if(pq[a].size()<pq[b].size()) swap(a,b);
        dsu[b]=a;
        while(!pq[b].empty()){
            if(vis[pq[b].top().second]){
                pq[b].pop();
            }
            else{
                pq[a].push(pq[b].top());
                pq[b].pop();
            }
        }
        rep[a]=rep[v];
        while(!pq[a].empty()){
            if(vis[pq[a].top().second]){
                pq[a].pop();
            }
            else{
                finpq.insert(make_pair(pq[a].top().first-s[rep[a]],a));
                pq[a].pop();
                break;
            }
        }
    }
    for(int i=0;i<=q;i++){
        if(i>=n) cout<<ans[n-1]<<"\n";
        else cout<<ans[i]<<"\n";
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 143 ms 40224 KB Output is correct
3 Correct 143 ms 40144 KB Output is correct
4 Execution timed out 4053 ms 40524 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 143 ms 40224 KB Output is correct
3 Correct 143 ms 40144 KB Output is correct
4 Execution timed out 4053 ms 40524 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 143 ms 40224 KB Output is correct
3 Correct 143 ms 40144 KB Output is correct
4 Execution timed out 4053 ms 40524 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 143 ms 40224 KB Output is correct
3 Correct 143 ms 40144 KB Output is correct
4 Execution timed out 4053 ms 40524 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 452 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 452 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 143 ms 40224 KB Output is correct
3 Correct 143 ms 40144 KB Output is correct
4 Execution timed out 4053 ms 40524 KB Time limit exceeded
5 Halted 0 ms 0 KB -