Submission #1287069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287069		trungcan	Sirni (COCI17_sirni)	C++17	14 / 140	5117 ms	828008 KiB

sirni

#include <bits/stdc++.h>
#define ar3 array<int, 3>
using namespace std;
const int N = 1e5 + 5, M = 1e7 + 5;
int n, cnt, pos[M], nxt[M], p[N], s[N], m, e, a[N];
long long ans;
vector<ar3> edge;
int get(int u){
    return p[u] == u ? u : p[u] = get(p[u]);
}
void unite(int u, int v){
    if (s[u] > s[v]) swap(u, v);
    s[v] += s[u];
    p[u] = v;
}
bool cmp(ar3 x, ar3 y){
    return x[2] < y[2];
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("MODST.INP", "r")){
        freopen("MODST.INP", "r", stdin);
        freopen("MODST.OUT", "w", stdout);
    }
    cin >> n;
    while (n--){
        int x; cin >> x;
        m = max(m, x);
        if (!pos[x]) a[pos[x] = ++cnt] = x;
    }
    for (int i = 1; i <= cnt; ++i) p[i] = i, s[i] = 1;
    for (int i = m; i > 0; --i)
        if (pos[i + 1]) nxt[i] = i + 1;
        else nxt[i] = nxt[i + 1];
    for (int i = 1; i <= cnt; ++i)
        for (int j = a[i]; j <= m; j += a[i]){
            if (nxt[j])
                edge.push_back({i, pos[nxt[j]], nxt[j] - j});
            int x = get(i), y = get(pos[j]);
            if (pos[j] && a[i] != j && x != y)
                unite(x, y), ++e;
        }
    sort(edge.begin(), edge.end(), cmp);
    if (e >= cnt - 1) cout << 0;
    else {
        for (ar3 x: edge){
            int u = get(x[0]), v = get(x[1]), w = x[2];
            if (u == v) continue;
            unite(u, v);
            ++e;
            ans += w;
            if (e == cnt - 1) break;
        }
        cout << ans;
    }
}

Compilation message (stderr)

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

• Subtask 1: 14 / 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