Submission #1167960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167960		Saul0906	Sirni (COCI17_sirni)	C++20	84 / 140	3250 ms	851968 KiB

sirni

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define rep(a,b,c) for(ll a=b; a<c; a++)
#define rep2(a,b,c,d) for(ll a=b; a<c; a+=d)
#define repr(a,b,c) for(ll a=b-1; a>c-1; a--)
#define repa(a,b) for(const auto &a: b)
#define multicase() int t=1; while(t--)
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define valid(c) cout<<(c ? "YES" : "NO")<<endl;
#define valid2(c,a,b) cout<<(c ? a : b)<<endl;
#define pq_min(a) priority_queue<a, vector<a>, greater<a>>
#define pq_max(a) priority_queue<a>
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mid ((l+r)>>1)
#define flush endl<<flush
#define all(a) a.begin(), a.end()
#define iii array<int, 3>

using namespace std;
using namespace __gnu_pbds;

using vi = vector<int>;
using ll = long long;
template <typename T>
using vec = vector<T>;
template <typename T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N=1e7+5;
vec<pii> edges[N];
vi nd[N];
int dsu[N];

int find(int u){
        if(dsu[u]==-1) return u;
        return dsu[u]=find(dsu[u]);
}

void join(int u, int v){
        u=find(u), v=find(v);
        dsu[u]=v;
}

int main(){
        fastIO();
        multicase(){
                int n;
                cin>>n;
                int a[n], mx=0, mn, ind=n-1;
                rep(i,0,n) cin>>a[i], mx=max(mx,a[i]);
                sort(a,a+n);
                int nxt[mx+1]{}, cont[mx+1]{};
                rep(i,0,n) cont[a[i]]=1;
                repr(i,mx+1,1){
                        nd[i].clear();
                        if(!cont[i]) continue;
                        rep2(j,i,mx+1,i){
                                nd[j].pb(i);
                                if(cont[j]) edges[0].pb({i,j});
                        }
                }
                mn=mx;
                repr(i,mx+1,1){
                        nxt[i]=mn;
                        while(ind>=0 && a[ind]==i) mn=a[ind--];
                        if(!nd[i].size()) continue;
                        bool z=1;
                        rep2(j,i+i,mx+1,i) if(nxt[i]==nxt[j]) z=0;
                        if(!z) continue;
                        while(nd[i].size()){
                                int u=nd[i].back();
                                edges[nxt[i]-i].pb({u,nxt[i]});
                                nd[i].ppb();
                        }
                }
                ll ans=0;
                fill(dsu,dsu+mx+1,-1);
                rep(i,0,mx+1){
                        repa(e,edges[i]) if(find(e.fi)!=find(e.se)) join(e.fi,e.se), ans+=i;
                        edges[i].clear();
                }
                cout<<ans<<endl;
        }
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14