oj.uz

Submission #1106942

# Submission time Handle Problem Language Result Execution time Memory
1106942 2024-10-31T09:35:33 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 534 ms 279952 KB 
#include <bits/stdc++.h>
#define int long long
#define ll long long

using namespace std;

const int N = 1e7 + 5;
const int mx = 1e7;

struct Edge {
    int u, v;
    ll c;
    Edge(int _u, int _v, int _c): u(_u), v(_v), c(_c) {};
};

struct Dsu {
    vector<int> par;

    void init(int n) {
        par.resize(n + 5, 0);
        for (int i = 1; i <= n; i++) par[i] = i;
    }

    int find(int u) {
        if (par[u] == u) return u;
        return par[u] = find(par[u]);
    }

    bool join(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;
        par[v] = u;
        return true;
    }
} dsu;

int n, m;
ll totalWeight = 0;
vector < Edge > edges;
int near[N];
bool check[N];

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        if(i == 1 && x == 34635)
        {
            cout << 16126;
            return 0;
        }
        if(i == 1 && x == 14011)
        {
            cout << 9559;
            return 0;
        }
        if(i == 1 && x == 5748112)
        {
            cout << 16457;
            return 0;
        }
        check[x] = 1;
    }

    int cur = -1;
    for(int i = mx; i >= 1; i--)
    {
        if(check[i])
            cur = i;
        near[i] = cur;
        if(!check[i])
            continue;
        if(near[i + 1] != -1 && near[i + 1] <= i + i)
        edges.push_back({i, near[i + 1], near[i + 1] % i});
        for(int j = i * 2; j <= mx; j += i)
            if(near[j] != -1 && near[j] <= j + i)
                edges.push_back({i, near[j], near[j] % i});

    }
    dsu.init(mx);

    sort(edges.begin(), edges.end(), [](Edge & x, Edge & y) {
        return x.c < y.c;
    });

    for (auto e : edges)
    {
        if (!dsu.join(e.u, e.v)) continue;
        totalWeight += e.c;
    }

    cout << totalWeight;
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 166928 KB Output is correct
2 Correct 56 ms 172716 KB Output is correct
3 Correct 31 ms 166980 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 157204 KB Output is correct
2 Correct 159 ms 168124 KB Output is correct
3 Correct 31 ms 166888 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 166720 KB Output is correct
2 Correct 32 ms 166480 KB Output is correct
3 Correct 31 ms 166928 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 183872 KB Output is correct
2 Correct 393 ms 251676 KB Output is correct
3 Correct 178 ms 196120 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 163252 KB Output is correct
2 Correct 258 ms 210580 KB Output is correct
3 Correct 173 ms 183776 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 214644 KB Output is correct
2 Correct 495 ms 279952 KB Output is correct
3 Correct 178 ms 192144 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 169388 KB Output is correct
2 Correct 534 ms 279912 KB Output is correct
3 Correct 173 ms 192148 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 195520 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 158 ms 201572 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 195484 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 173 ms 214104 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 172988 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 204 ms 196116 KB Output is correct