Submission #1095526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095526		0pt1mus23	Sirni (COCI17_sirni)	C++14	0 / 140	637 ms	265008 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ins insert
#define pb push_back
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
#define _ << " " <<  
const int   mod = 1e9+7 ,
            sze= 1e7 +25 ,
            inf = INT_MAX ,
            L = 31 ;
// credit : aykhn
int parent[sze];
int sz[sze];
int root(int node){
    if(parent[node]==node){
        return node;
    }
    return parent[node]=root(parent[node]);
}
int unite(int a,int b){
    int x = root(a);
    int y = root(b);
    if(x==y){
        return 0;
    }
    if(sz[y]>sz[x]){
        swap(y,x);
    }
    parent[y]=x;
    sz[x]+=sz[y];
    return 1;
}
 
vector<pair<int,int>> event[sze];
void opt1z(){
    int n;
    cin>>n;
    for(int i=0;i<=(int)n+23;i++){
        sz[i]=1;
        parent[i]=i;
    }
    int ans=0;
 
    vector<int> arr(n);
    set<pair<int,int>> lst;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        lst.ins({arr[i],i});
    }
    sort(all(arr));
    
    int mx = arr.back();
 
    for(auto v:lst){
        int c =v.first;
        int i= v.second;
        while(c<=mx){
            auto it = lst.end();
            if(c==v.first){
                it = lst.upper_bound({c,inf});
            }  
            else{
                it = lst.lower_bound({c,-1});
            }
            if(it==lst.end()){
                break;
            }
            // cout<<v _ " ," _  c _ *it % v <<endl;

            event[ (*it).first % v.first ].pb({i,(*it).second});
            c = ((*it).first / v.first +1) * v.first;
        }
    }
    for(int i =0;i<=mx;i++){
        for(auto v:event[i]){
            // cout<<i _ v.first _ "=> " _ v.second<<endl;
            if(unite(v.first,v.second)){
                ans+=i;
            }
        }
    }
 
 
    putr(ans);
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }
 
    return 0;
}

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