Submission #889311

#	Time	Username	Problem	Language	Result	Execution time	Memory
889311		dimashhh	Sirni (COCI17_sirni)	C++17	140 / 140	3106 ms	769192 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 998244353,MAX = 1e7 + 1;
typedef long long ll;

int n,a[N],p[MAX];
vector<ll> b;
vector<pair<int,int>> g[MAX];
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
void merge(int v,int u){
    v = get(v);
    u = get(u);
    p[v] = u;
}
void add(int x){
    for(int i = 0;true;i++){
        if(i * x > b.back()) break;
        int it = lower_bound(b.begin(),b.end(),x * i) - b.begin();
        if(b[it] == x) it++;
        if(it < (int)b.size()){
            int val = min(b[it] % x,x % b[it]);
            // cout << val << ' ' << x << ' ' << b[it] << '\n';
            g[val].push_back({x,b[it]});
        }
    }
}
void test(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    for(int i = 1;i < MAX;i++){
        p[i] = i;
    }
    sort(a + 1,a + n + 1);
    for(int i = 1;i <= n;i++){
        if(a[i] != a[i - 1]){
            b.push_back(a[i]);
        }
    }
    for(auto i:b){
        add(i);
    }
    ll ans = 0;
    for(int i = 0;i < MAX;i++){
        for(auto [x,y]:g[i]){
            if(get(x) != get(y)){
                ans += i;
                merge(x,y);
            }
        }
    }
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

• 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