oj.uz

Submission #1004496

# Submission time Handle Problem Language Result Execution time Memory
1004496 2024-06-21T09:27:53 Z Huseyn123 Sirni (COCI17_sirni) C++17
140 / 140
 2336 ms 722432 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
  #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int ll
#define MAX 100001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second 

#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << endl;\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << (int)x << " ";\
    }\
    cout << endl;\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
int n,q,t=1,m,k,x,y,z,x2,y2,z2;
vector<int> a;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string s[MAX],str[MAX];
//int e[1001][1001];
string s1,s2,s3;
const int mod = 998244353;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
struct DSU{
    vector<int> e;
    DSU(int N){ e=vector<int>(N+1,-1);}
    int get(int x){return e[x]<0 ? x : e[x]=get(e[x]);}
    bool same_set(int x,int y){ return get(x)==get(y);}
    int size(int x){return -e[get(x)];}
    bool unite(int x,int y){
        x=get(x);
        y=get(y);
        if(x==y) return false;
        if(e[x]>e[y]) swap(x,y);
        e[x]+=e[y]; e[y]=x;
        return true;
    }
};
int N=5e6;
vector<vector<pii>> edges(N);
void solve(){
    cin >> n; 
    a.clear();
    a.resize(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int mx=0;
    sortv(a);
    a.erase(unique(all(a)),a.end());
    n=(int)a.size();
    mx=a[n-1];
    for(int i=0;i<n;i++){
        for(int j=a[i];j<=mx;j+=a[i]){
            auto it=lb(a,j);
            if(it-a.begin()==i){
                ++it;
            }
            if(it!=a.end()){
                if(*it-j<a[i]){
                    edges[*it-j].pb({it-a.begin(),i});
                }
            }
        }
    }
    DSU dsu(n);
    int res=0;
    for(int i=0;i<N;i++){
        for(auto x:edges[i]){
            res+=dsu.unite(x.ff,x.ss)*i;
        }
    }
    cout << res << "\n";
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("input13.txt","r",stdin);
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++; 
    }
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 124240 KB Output is correct
2 Correct 87 ms 129056 KB Output is correct
3 Correct 58 ms 124496 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 124240 KB Output is correct
2 Correct 407 ms 125444 KB Output is correct
3 Correct 74 ms 124240 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 124060 KB Output is correct
2 Correct 53 ms 123996 KB Output is correct
3 Correct 54 ms 124240 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 144000 KB Output is correct
2 Correct 384 ms 197400 KB Output is correct
3 Correct 169 ms 154076 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 127312 KB Output is correct
2 Correct 174 ms 167276 KB Output is correct
3 Correct 137 ms 143576 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 168136 KB Output is correct
2 Correct 457 ms 226548 KB Output is correct
3 Correct 168 ms 150692 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 130928 KB Output is correct
2 Correct 397 ms 216296 KB Output is correct
3 Correct 168 ms 150076 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 147512 KB Output is correct
2 Correct 1831 ms 540452 KB Output is correct
3 Correct 195 ms 152692 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 148564 KB Output is correct
2 Correct 2336 ms 722432 KB Output is correct
3 Correct 285 ms 162164 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 128592 KB Output is correct
2 Correct 2053 ms 712944 KB Output is correct
3 Correct 174 ms 154368 KB Output is correct