oj.uz

답안 #1057658

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1057658 2024-08-14T02:43:18 Z vjudge1 Sirni (COCI17_sirni) C++17
140 / 140
 466 ms 279420 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

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 166936 KB Output is correct
2 Correct 45 ms 172744 KB Output is correct
3 Correct 26 ms 166992 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 157296 KB Output is correct
2 Correct 138 ms 168036 KB Output is correct
3 Correct 27 ms 167068 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 166680 KB Output is correct
2 Correct 26 ms 166484 KB Output is correct
3 Correct 26 ms 166932 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 183732 KB Output is correct
2 Correct 328 ms 252052 KB Output is correct
3 Correct 172 ms 194464 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 164544 KB Output is correct
2 Correct 220 ms 210072 KB Output is correct
3 Correct 144 ms 183724 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 230 ms 214036 KB Output is correct
2 Correct 466 ms 279420 KB Output is correct
3 Correct 148 ms 192112 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 168584 KB Output is correct
2 Correct 439 ms 278924 KB Output is correct
3 Correct 159 ms 191240 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 195492 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 119 ms 202024 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 196000 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 141 ms 212664 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 172224 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 156 ms 195820 KB Output is correct