Submission #1264908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264908		menkh	Sirni (COCI17_sirni)	C++17	140 / 140	4233 ms	395328 KiB

sirni

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

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)

#define MAX 100005
int parent[MAX];
int n, Max = 0;

struct menkh {
    int u, v, w;
};

vector<menkh> adj;

int root(int v) {
    return v == parent[v] ? v : parent[v] = root(parent[v]);
}

bool unite(int u, int v) {
    u = root(u), v = root(v); 
    if (u == v) return false;
    parent[v] = u;
    return true;
}

void solve() {
    scanf("%d", &n); 
    vector<int> p(n + 1);
    FOR(i, 1, n) {
        scanf("%d", &p[i]); 
        Max = max(p[i], Max);
    }

    sort(p.begin() + 1, p.end());
    p.erase(unique(p.begin() + 1, p.end()), p.end());
    n = p.size() - 1;
    FOR(i, 1, n) parent[i] = i;

    FOR(i, 1, n) {
        for (int k = 1; k * p[i] <= Max; k++) {
            int v = lower_bound(p.begin() + 1, p.begin() + n + 1, k * p[i]) - p.begin();
            if (v == i) v = i + 1;
            if (v > n) break;
            if (p[v] <= (k + 1) * p[i]) adj.push_back({i, v, p[v] % p[i]});
        }
    }

    sort(adj.begin(), adj.end(), [](menkh A, menkh B) {
        return A.w < B.w;
    });

    long long answer = 0;
    REP(i, (int)adj.size()) {
        if (unite(adj[i].u, adj[i].v)) answer += adj[i].w;
    }

    printf("%lld\n", answer);
}

int main() {
    solve();
}

Compilation message (stderr)

sirni.cpp: In function 'void solve()':
sirni.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
sirni.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d", &p[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