Submission #1239922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239922		Sang	Sirni (COCI17_sirni)	C++20	140 / 140	3387 ms	198552 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, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int n, lab[N];

int Find(int u){
    return lab[u] < 0 ? u : lab[u] = Find(lab[u]);
}

int join(int u, int v){
    if ((u = Find(u)) == (v = Find(v))) return 0;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return 1;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n;
    memset(lab, -1, sizeof lab);
    vector<int> a;
    FOR (i, 1, n){
        int x; cin >> x;
        a.pb(x);
    }
    a.pb(0);
    sort(ALL(a));
    a.resize(unique(ALL(a)) - a.begin());
    vector<pii> edges;
    FOR (i, 1, (int)a.size() - 2){
        for (int j = 1; a[i] * j <= a.back(); j++){
            int x = lower_bound(ALL(a), a[i] * j) - a.begin();
            if (x == i) ++x;
            if (a[x]%a[i] >= a[1]) continue;
            edges.pb({a[x]%a[i], {i, x}});
        }
    }
    sort(ALL(edges));
    long long ans = 0;
    for (pii &x : edges){
        if (join(x.se.fi, x.se.se)) ans += x.fi;
    }
    cout << ans;
    

    return 0;
}

Compilation message (stderr)

sirni.cpp: In function 'int main()':
sirni.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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