Submission #788134

#	Time	Username	Problem	Language	Result	Execution time	Memory
788134		model_code	Security Guard (JOI23_guard)	C++17	100 / 100	543 ms	111104 KiB

guard

#include <bits/stdc++.h>
using namespace std;

#define SIZE_N 200005
#define SIZE_M 400005
#define INFL LLONG_MAX/3

using ll=long long;

struct edge{
    ll a,b,c;
    bool operator<(const edge p)const{
        if(c!=p.c)return c<p.c;
        if(a!=p.a)return a<p.a;
        return b<p.b;
    }
    bool operator>(const edge p)const{
        if(c!=p.c)return c>p.c;
        if(a!=p.a)return a>p.a;
        return b>p.b;
    }
};

struct UnionFind{
    int par[SIZE_N];
    void init(int n){
        for(int i=0;i<n;i++){
            par[i]=i;
        }
    }
    int find(int x){
        if(x==par[x])return x;
        return par[x]=find(par[x]);
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
    void unit(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return;
        par[x]=y;
    }
}uf;

ll n,m,q,s[SIZE_N],ans,ma,sum,d[SIZE_N],miv;
edge e[SIZE_M];
pair<ll,ll>mi=make_pair(INFL,-1);
vector<ll>ansrev;
bool con[SIZE_N];
vector<edge>g;

struct all_edge{
    ll a,b,par,c;
    bool operator<(const all_edge p)const{
        if(c!=p.c)return c<p.c;
        if(par!=p.par)par<p.par;
        if(a!=p.a)return a<p.a;
        return b<p.b;
    }
    bool operator>(const all_edge p)const{
        if(c!=p.c)return c>p.c;
        if(par!=p.par)par>p.par;
        if(a!=p.a)return a>p.a;
        return b>p.b;
    }
};

ll pa[SIZE_N],toe[SIZE_N];
priority_queue<edge,vector<edge>,greater<edge>>have[SIZE_N];
priority_queue<all_edge,vector<all_edge>,greater<all_edge>>all;

ll find_pa(ll x){
    if(x==pa[x])return x;
    return pa[x]=find_pa(pa[x]);
}

int main(void){
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=0;i<n;i++){
        scanf("%lld",&s[i]);
        ma=max(ma,s[i]);
        mi=min(mi,make_pair(s[i],ll(i)));
        sum+=s[i];
    }
    miv=mi.second;
    for(int i=0;i<m;i++){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        a--,b--;
        if(a>b)swap(a,b);
        e[i]=edge{a,b,s[a]+s[b]};
    }
    sort(e,e+m);
    uf.init(n);
    for(int i=0;i<m;i++){
        ll a=e[i].a,b=e[i].b;
        if(!uf.same(a,b)){
            ans+=e[i].c;
            uf.unit(a,b);
            g.push_back(e[i]);
        }
    }
    for(auto i:g){
        if(i.a==miv)con[i.b]=true;
        else if(i.b==miv)con[i.a]=true;
        else{
            have[i.a].push(edge{i.a,i.b,i.c});
            have[i.b].push(edge{i.b,i.a,i.c});
        }
    }
    for(int i=0;i<n;i++){
        pa[i]=i;
        toe[i]=i;
        if(!con[i]&&!have[i].empty()){
            edge x=have[i].top();
            all.push(all_edge{x.a,x.b,x.a,-(s[miv]+s[x.a])+x.c});
        }
    }
    ll start=(n-2)*mi.first+sum;
    ansrev.push_back(start);
    while(!all.empty()){
        all_edge al=all.top();
        ll a=all.top().a,b=all.top().b,c=all.top().c,d=all.top().par;
        all.pop();
        if(find_pa(a)==find_pa(b)||find_pa(a)!=d)continue;
        start+=c;
        ansrev.push_back(start);
        a=find_pa(a);
        b=find_pa(b);
        ll x=toe[a],y=toe[b];
        if(have[x].size()>have[y].size())swap(x,y);
        while(!have[x].empty()){
            have[y].push(have[x].top());
            have[x].pop();
        }
        pa[a]=b;
        if(con[b])continue;
        toe[b]=y;
        while(!have[y].empty()&&find_pa(have[y].top().a)==find_pa(have[y].top().b))have[y].pop();
        if(!have[y].empty())all.push(all_edge{have[y].top().a,have[y].top().b,b,-(s[miv]+s[b])+have[y].top().c});
    }
    reverse(ansrev.begin(),ansrev.end());
    for(int i=0;i<=q;i++){
        if(ansrev.size()<=i)printf("%lld\n",ansrev.back()-sum+ma);
        else printf("%lld\n",ansrev[i]-sum+ma);
    }
}

Compilation message (stderr)

guard.cpp: In member function 'bool all_edge::operator<(all_edge) const':
guard.cpp:57:26: warning: statement has no effect [-Wunused-value]
   57 |         if(par!=p.par)par<p.par;
      |                       ~~~^~~~~~
guard.cpp: In member function 'bool all_edge::operator>(all_edge) const':
guard.cpp:63:26: warning: statement has no effect [-Wunused-value]
   63 |         if(par!=p.par)par>p.par;
      |                       ~~~^~~~~~
guard.cpp: In function 'int main()':
guard.cpp:123:18: warning: variable 'al' set but not used [-Wunused-but-set-variable]
  123 |         all_edge al=all.top();
      |                  ^~
guard.cpp:145:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  145 |         if(ansrev.size()<=i)printf("%lld\n",ansrev.back()-sum+ma);
      |            ~~~~~~~~~~~~~^~~
guard.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |     scanf("%lld%lld%lld",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
guard.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%lld",&s[i]);
      |         ~~~~~^~~~~~~~~~~~~~
guard.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%lld%lld",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

• 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