oj.uz

Submission #1095520

# Submission time Handle Problem Language Result Execution time Memory
1095520 2024-10-02T13:13:51 Z 0pt1mus23 Sirni (COCI17_sirni) C++14
98 / 140
 5000 ms 786432 KB 
#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*2 +23 ,
            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)1e7;i++){
        sz[i]=1;
        parent[i]=i;
    }
    int ans=0;

    vector<int> arr(n);
    set<int> lst;
    map<int,int> idx;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        idx[arr[i]]=i;
        lst.ins(arr[i]);
    }
    sort(all(arr));
    
    vector<int> yuxari;
    int mx = arr.back() *2;
    

    for(auto v:lst){
        int c =v;
        int i= idx[v];
        while(c<=mx){
            auto it = lst.end();
            if(c==v){
                it = lst.upper_bound(c);
            }  
            else{
                it = lst.lower_bound(c);
            }
            if(it==lst.end()){
                break;
            }
            // cout<<v _ " ," _  c _ *it % v <<endl;
            int ib = idx[*it];
            event[ (*it) % v ].pb({i,ib});
            c = ((*it) / v) * v;
            c+=v;
        }
    }
    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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 548436 KB Output is correct
2 Correct 239 ms 550812 KB Output is correct
3 Correct 248 ms 548692 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 548432 KB Output is correct
2 Correct 245 ms 549204 KB Output is correct
3 Correct 229 ms 548744 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 548436 KB Output is correct
2 Correct 254 ms 548432 KB Output is correct
3 Correct 238 ms 548524 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 567756 KB Output is correct
2 Correct 1419 ms 594344 KB Output is correct
3 Correct 575 ms 571232 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 551220 KB Output is correct
2 Correct 395 ms 571728 KB Output is correct
3 Correct 502 ms 566288 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 579956 KB Output is correct
2 Correct 1523 ms 609332 KB Output is correct
3 Correct 585 ms 571008 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 555192 KB Output is correct
2 Correct 1176 ms 602060 KB Output is correct
3 Correct 598 ms 569700 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 570824 KB Output is correct
2 Execution timed out 5082 ms 759744 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 570532 KB Output is correct
2 Runtime error 4958 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 552528 KB Output is correct
2 Runtime error 4511 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -