Submission #927910

#	Time	Username	Problem	Language	Result	Execution time	Memory
927910		Beerus13	Sirni (COCI17_sirni)	C++14	140 / 140	1448 ms	669112 KiB

sirni

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14