Submission #1214174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214174		giabao249	Sirni (COCI17_sirni)	C++20	70 / 140	5117 ms	851968 KiB

sirni

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define el '\n'
#define pii pair<int , int>
const int N = 1e5 + 5;
const int inf = 1e18;
int n, par[N];
struct node {
    int u, v, w;
    bool operator < (node &other) const {
        return w < other.w;
    }
};
int get(int v) {
    return v == par[v] ? v : par[v] = get(par[v]);
}
bool unite(int u, int v) {
    u = get(u);
    v = get(v);
    if(u == v) return 0;
    par[v] = u;
    return 1;
}
void solve() {
    cin >> n;
    vector<int> a(n);
    map<int, int> pos;
    int M = 0;
    for(int i = 0 ; i < n ; i++) {
        cin >> a[i];
        pos[a[i]] = i + 1;
        M = max(M, a[i]);
    }
    sort(a.begin(), a.end());
    for(int i = 1 ; i <= n ; i++) par[i] = i;
    vector<node> edge;
    for(int i = 0 ; i < n ; i++) {
        int k = 1;
        while(k * a[i] <= M) {
            vector<int>::iterator q;
            if(k == 1) {
                q = upper_bound(a.begin(), a.end(), k * a[i]);
            } else {
                q = lower_bound(a.begin(), a.end(), k * a[i]);
            }
            if(q != a.end()) {
                int p = q - a.begin();
                int u = pos[a[i]];
                int v = pos[a[p]];
                if(u == v) {
                    k++;
                    continue;
                }
                if (a[i] != 0 && a[p] != 0) {
                    int w = min(a[i] % a[p], a[p] % a[i]);
                    edge.push_back({u, v, w});
                }
            }
            k++;
        }
    }
    int ans = 0;
    sort(edge.begin(), edge.end());
    for(auto [u, v, w] : edge) {
        if(unite(u, v)) ans += w;
    }
    cout << ans << el;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14