Submission #676799

#	Time	Username	Problem	Language	Result	Execution time	Memory
676799		zjsxzy	Sirni (COCI17_sirni)	C++17	0 / 140	253 ms	50664 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

struct union_find{
    int N;
    vector<int> par, siz;
    union_find(int n) : N(n){
        par.resize(N);
        siz.resize(N, 1);
        for(int i=0; i<N; i++) par[i] = i;
    }
    int root(int X){
        if(par[X] == X) return X;
        return par[X] = root(par[X]);
    }
    bool same(int X, int Y){
        return root(X) == root(Y);
    }
    void unite(int X, int Y){
        X = root(X);
        Y = root(Y);
        if(X == Y) return;
        if(siz[Y] < siz[X]) std::swap(X, Y);
        par[X] = Y;
        siz[Y] += siz[X];
        siz[X] = 0;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }
    sort(p.begin(), p.end());
    p.resize(unique(p.begin(), p.end()) - p.begin());
    int mx = p[p.size() - 1];
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < (int)p.size(); i++) {
        int x = p[i];
        for (int l = x; l <= mx; l += x) {
            auto it = lower_bound(p.begin(), p.end(), l) - p.begin();
            if (it != i && it < (int)p.size() && p[it] < 2 * l) {
                edges.push_back({p[it] % x, {i, it}});
            }
        }
    }
    union_find dsu(n);
    LL res = 0;
    for (int i = 0; i < (int)edges.size(); i++) {
        int u = edges[i].second.first, v = edges[i].second.second, w = edges[i].first;
        if (dsu.same(u, v)) continue;
        res += w;
        dsu.unite(u, v);
    }
    cout << res << endl;
}

int main() {
    int ts = 1;
    // cin >> ts;
    for (int t = 1; t <= ts; t++) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'void solve()':
sirni.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d", &p[i]);
      |         ~~~~~^~~~~~~~~~~~~

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