oj.uz

Submission #927910

# Submission time Handle Problem Language Result Execution time Memory
927910 2024-02-15T13:59:25 Z Beerus13 Sirni (COCI17_sirni) C++14
140 / 140
 1448 ms 669112 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1e5 + 5;
const int maxn = 1e7 + 5;

int n, a[N], Next[maxn];
bool exist[maxn];
int par[maxn], sz[maxn];
vector<pii> g[maxn];

int find(int u) {
    if(u == par[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 true;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
    return false;
}

void solve() {
    cin >> n;
    int Max = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        Next[a[i]] = a[i];
        Max = max(Max, a[i]);
        exist[a[i]] = 1;
    }
    for(int i = Max; i >= 0; --i) {
        if(!exist[i]) Next[i] = Next[i + 1];
    }
    for(int i = 1; i <= n; ++i) {
        if(!exist[a[i]]) continue;
        int x = a[i];
        for(int j = 1; j <= Max / x; ++j) {
            int y = (j == 1) ? x + 1 : x * j;
            y = Next[y];
            if(x * (j + 1) > y) g[y % x].emplace_back(y, x);   
        }
        exist[a[i]] = 0; // duyet 1 lan
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) par[a[i]] = a[i], sz[a[i]] = 1;
    for(int i = 0; i <= Max; ++i) {
        for(auto [u, v] : g[i]) {
            if(!join(u, v)) ans += i;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
}

/*
    g[i] : cách cạnh có độ dài i
    y > x -> giá trị cạnh = y % x
    -> Max = max(a[i])
    với mỗi node giá trị x, duyệt bội của x -> y = k * x <= Max
                                            tìm số gần y nhất xuất hiện -> push cạnh 
    -> tìm cây khung nhỏ nhất
*/

Compilation message

sirni.cpp: In function 'void solve()':
sirni.cpp:52:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         for(auto [u, v] : g[i]) {
      |                  ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 362432 KB Output is correct
2 Correct 137 ms 364876 KB Output is correct
3 Correct 115 ms 362664 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 243120 KB Output is correct
2 Correct 300 ms 363056 KB Output is correct
3 Correct 115 ms 362576 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 362580 KB Output is correct
2 Correct 104 ms 350036 KB Output is correct
3 Correct 105 ms 362672 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 265180 KB Output is correct
2 Correct 138 ms 293204 KB Output is correct
3 Correct 93 ms 270496 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 256592 KB Output is correct
2 Correct 116 ms 278132 KB Output is correct
3 Correct 80 ms 259480 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 276300 KB Output is correct
2 Correct 157 ms 304224 KB Output is correct
3 Correct 92 ms 268436 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 246384 KB Output is correct
2 Correct 151 ms 303052 KB Output is correct
3 Correct 89 ms 267624 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 375944 KB Output is correct
2 Correct 938 ms 581640 KB Output is correct
3 Correct 186 ms 378304 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 375444 KB Output is correct
2 Correct 1295 ms 669112 KB Output is correct
3 Correct 203 ms 382280 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 364880 KB Output is correct
2 Correct 1448 ms 666372 KB Output is correct
3 Correct 94 ms 270472 KB Output is correct