oj.uz

Submission #990743

# Submission time Handle Problem Language Result Execution time Memory
990743 2024-05-31T07:07:07 Z KawakiMeido Sirni (COCI17_sirni) C++17
98 / 140
 692 ms 786532 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define int long long
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int M = 1e7+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n;
vector<int> a;
vector<piii> edge;
set<int> st;
int vis[M];
int nxt[M];

//DSU
int parent[N];

int Find(int x){
    return (x == parent[x]) ? x : parent[x] = Find(parent[x]);
}

void Union(int u, int v){
    int x = Find(u);
    int y = Find(v);
    if (x!=y){
        parent[y] = x;
    }
}

/*Solution*/
void solve(){
    cin >> n;
    int mx = 0;
    int mn = LLINF;
    int cnt = 0;
    for (int i=1; i<=n; i++){
        int x;
        cin >> x;
        if (!vis[x]){
            ++cnt;
            vis[x] = cnt;;
            a.push_back(x);
            mx = max(mx,x);
            mn = min(mn,x);
        }
    }
    st.insert(LLINF);
    sort(a.begin(),a.end());
    int rawr = INF;
    for (int i=mx+1; i>=1; i--){
        if (vis[i]) rawr = i;
        nxt[i] = rawr;
    }
    for (int idx = 0; idx<(int)a.size(); idx++){
        int x = a[idx];
        for (int i=x; i<=mx; i+=x){
            if (i == x){
                if (nxt[i+1]<i+x){
                    edge.push_back({nxt[i+1]-i,{x,nxt[i+1]}});
                }
            }
            else{
                if (nxt[i]<i+x){
                    edge.push_back({nxt[i]-i,{x,nxt[i]}});
                }
            }
        }
    }
    for (int i=1; i<=cnt; i++){
        parent[i] = i;
    }
    sort(edge.begin(),edge.end());
    int ans = 0;
    for (auto in:edge){
        int w = in.fi;
        int u = vis[in.se.fi];
        int v = vis[in.se.se];

//        cout << in.se.fi << " " << in.se.se << " " << w << endl;

        if (Find(u)!=Find(v)){
            ans+=w;
            Union(u,v);
        }
    }
    cout << ans;
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 84056 KB Output is correct
2 Correct 45 ms 89596 KB Output is correct
3 Correct 16 ms 84316 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 144 ms 82016 KB Output is correct
3 Correct 22 ms 84504 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 84568 KB Output is correct
2 Correct 14 ms 83036 KB Output is correct
3 Correct 21 ms 84400 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 45816 KB Output is correct
2 Correct 555 ms 119192 KB Output is correct
3 Correct 208 ms 71608 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 26376 KB Output is correct
2 Correct 264 ms 115932 KB Output is correct
3 Correct 147 ms 37820 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 120660 KB Output is correct
2 Correct 692 ms 218524 KB Output is correct
3 Correct 209 ms 70588 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 19660 KB Output is correct
2 Correct 658 ms 217492 KB Output is correct
3 Correct 186 ms 70328 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 209492 KB Output is correct
2 Runtime error 534 ms 786532 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 211824 KB Output is correct
2 Runtime error 530 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 75 ms 136960 KB Output is correct
2 Runtime error 485 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -