Submission #1274860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274860		chanhchuong123	Sirni (COCI17_sirni)	C++20	140 / 140	1189 ms	588336 KiB

sirni

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

const bool multiTest = false;
#define task "C"
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)

template<typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) a = b; else return 0; return 1;
}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) a = b; else return 0; return 1;
}

const int LIM = 10000010;
int N;
int cnt[LIM];
int lab[LIM];
int nxt[LIM];
vector<pair<int, int>> edges[LIM >> 1];

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

bool unionSet(int u, int v) {
    if ((u = findSet(u)) == (v = findSet(v))) return false;
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
}

void process(void) {
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        int P;
        cin >> P;
        ++cnt[P];
    }

    nxt[LIM - 9] = -1;
    for (int i = LIM - 10; i >= 1; --i) {
        nxt[i] = (cnt[i] == 0 ? nxt[i + 1] : i);
    }

    for (int i = 1; nxt[i + 1] != -1; ++i) if (cnt[i] > 0) {
        int pre = nxt[i + 1];
        edges[pre % i].emplace_back(i, pre);
        for (int j = i << 1; j <= LIM - 10 && nxt[j] != -1; j += i) {
            if (nxt[j] != pre)
                edges[nxt[j] % i].emplace_back(i, nxt[j]);
        }
    }

    memset(lab, -1, sizeof lab);
    long long ans = 0;

    for (int i = 0; i <= 5000000; ++i) {
        for (auto &[u, v]: edges[i]) if (unionSet(u, v)) {
            ans += i;
        }
    }
    cout << ans;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r",  stdin);
		freopen(task".out", "w", stdout);
	}

	int nTest = 1; if (multiTest) cin >> nTest;
	while (nTest--) {
		process();
	}

	return 0;
}

Compilation message (stderr)

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