Submission #1262156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262156		khoile08	Sirni (COCI17_sirni)	C++20	140 / 140	1484 ms	746588 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define FOD(i,a,b) for(int i = a; i >= b; i--)
//#define int long long
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define db double
#define lcm(a,b) a / __gcd(a, b) * b
#define ii pair<int,int>
#define iii pair<int,pair<int,int>>
#define iv pair<pair<int,int>,pair<int,int>>
#define sq(a) (a) * (a)
#define MASK(i) (1LL << i)
#define task "task"

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int P = 1e7;

int n;
vector<int> a;
int best[P + 5];
vector<ii> candi[P + 5];

int root[N], sze[N];

void init() {
    FOR(i, 0, (int)a.size() - 1) {
        root[i] = i;
        sze[i] = 1;
    }
}

int anc(int u) {
    return root[u] == u ? u : root[u] = anc(root[u]);
}

ll ans;

void join(int u, int v, int w) {
    u = anc(u);
    v = anc(v);
    if(u == v) return;
    ans += w;
    if(sze[u] < sze[v]) swap(u, v);
    root[v] = u;
    sze[u] += sze[v];
}

void KhoiLe() {
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int mx = a.back();
    FOR(i, 1, mx) best[i] = -1;
    FOR(i, 0, (int)a.size() - 1) best[a[i]] = i;
    FOD(i, mx - 1, 1) if(best[i] == -1) best[i] = best[i + 1];
    FOR(i, 0, (int)a.size() - 2) {
        candi[a[i + 1] % a[i]].pb({i, i + 1});
        for(int j = 2 * a[i]; j <= mx; j += a[i]) {
            if(best[j] != -1) candi[a[best[j]] % a[i]].pb({i, best[j]});
        }
    }
    init();
    FOR(i, 0, mx) for(auto H : candi[i]) join(H.fi, H.se, i);
    cout << ans << '\n';
}

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

    int test = 1;
//    cin >> test;
    while(test--) {
        cin >> n;
        FOR(i, 1, n) {
            int x;
            cin >> x;
            a.pb(x);
        }
        KhoiLe();
    }
}

• 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