oj.uz

Submission #1106833

# Submission time Handle Problem Language Result Execution time Memory
1106833 2024-10-31T07:37:11 Z baotoan655 Sirni (COCI17_sirni) C++14
140 / 140
 1760 ms 750744 KB 
#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REV(i, b, a) for(int i = (b); i >= (a); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define ll long long
#define fi first
#define se second

using namespace std;

const int N = 1e5 + 5;
int n;
int fa[N];
vector<int> ve;

void solve(int tc) {
    // cout << "Case #" << tc << ": ";
    cin >> n;
    REP(i, n) {
        int x;
        cin >> x;
        ve.emplace_back(x);
    }
    sort(ve.begin(), ve.end());
    ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
    n = ve.size();

    function<int(int)> root = [&](int x) -> int {
        if(x == fa[x]) return x;
        return fa[x] = root(fa[x]);
    };
    function<bool(int, int)> join = [&](int u, int v) -> bool {
        u = root(u); v = root(v);
        if(u == v) return false;
        fa[root(u)] = root(v);
        return true;
    };
    REP(i, n) fa[i] = i;
    int lim = ve.back();
    vector<int> pos(lim + 1, -1);
    REP(i, n) {
        pos[ve[i]] = i;
    }
    for(int i = lim - 1; i >= 0; --i) {
        if(pos[i] == -1) pos[i] = pos[i + 1];
    }

    vector<vector<pair<int, int>>> edge(lim);

    REP(i, n - 1) {
        edge[ve[i + 1] % ve[i]].emplace_back(i, i + 1);
        for(int j = 2 * ve[i]; j <= lim; j += ve[i]) {
            int nxt = pos[j];
            edge[ve[nxt] % ve[i]].emplace_back(i, nxt);
        }
    }
    int ans = 0;
    FOR(i, 0, lim - 1) {
        for(auto e : edge[i]) {
            if(join(e.fi, e.se)) {
                ans += i;
            }
        }
    }
    cout << ans << '\n';
    return;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    for(int i = 1; i <= tc; ++i) solve(i);
    return (0);
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 274208 KB Output is correct
2 Correct 149 ms 302408 KB Output is correct
3 Correct 64 ms 273568 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 1403 ms 679344 KB Output is correct
3 Correct 64 ms 275016 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 274352 KB Output is correct
2 Correct 62 ms 273736 KB Output is correct
3 Correct 62 ms 274380 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 38560 KB Output is correct
2 Correct 159 ms 73796 KB Output is correct
3 Correct 83 ms 51380 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29776 KB Output is correct
2 Correct 89 ms 51020 KB Output is correct
3 Correct 62 ms 25736 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 54392 KB Output is correct
2 Correct 185 ms 92512 KB Output is correct
3 Correct 79 ms 50776 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9784 KB Output is correct
2 Correct 195 ms 88224 KB Output is correct
3 Correct 81 ms 52976 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 287944 KB Output is correct
2 Correct 1336 ms 636776 KB Output is correct
3 Correct 158 ms 292552 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 292800 KB Output is correct
2 Correct 1760 ms 750744 KB Output is correct
3 Correct 302 ms 349692 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 276592 KB Output is correct
2 Correct 1510 ms 637332 KB Output is correct
3 Correct 94 ms 58520 KB Output is correct