제출 #490254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
490254		BeanZ	Sirni (COCI17_sirni)	C++14	140 / 140	4127 ms	512416 KiB

sirni

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld long double
#define endl '\n'
const int N = 1e7 + 5;
const int mod = 1e9 + 7;
const int mod2 = 998244353;
const long long lim = 1e7;
const int lg = 18;
const int base = 311;
const int base2 = 511;
const long double eps = 1e-6;
ll ans = 0;
ll p[N], a[N], oke[N], nx[N];
struct viet{
    ll u, v, c;
};
bool cmp(viet x, viet y){
    return x.c < y.c;
}
ll find_set(ll u){
    if (p[u] < 0) return u;
    return p[u] = find_set(p[u]);
}
void dsu(ll u, ll v, ll c){
    //cout << u << " " << v << " " << c << endl;
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (p[u] > p[v]) swap(u, v);
    p[u] += p[v];
    p[v] = u;
    ans += c;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n;
    cin >> n;
    memset(p, -1, sizeof(p));
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        oke[a[i]] = 1;
    }
    ll last = 0;
    for (int i = lim; i >= 1; i--){
        if (oke[i]) last = i;
        nx[i] = last;
    }
    vector<viet> E;
    for (int i = 1; i <= lim; i++){
        if (oke[i]){
            if (nx[i + 1]) E.push_back({i, nx[i + 1], nx[i + 1] - i});
            for (int j = i; j <= lim; j += i){
                if (nx[j] == 0) break;
                if ((j + i) <= nx[j]) continue;
                E.push_back({i, nx[j], nx[j] - j});
            }
        }
    }
    sort(E.begin(), E.end(), cmp);
    for (auto j : E){
        dsu(j.u, j.v, j.c);
    }
    cout << ans;
}
/*
2
10000000
9999999
Ans:

Out:
*/

컴파일 시 표준 에러 (stderr) 메시지

sirni.cpp: In function 'int main()':
sirni.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sirni.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("test.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