Submission #1018427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018427		GentleRage	Sirni (COCI17_sirni)	C++17	140 / 140	1006 ms	747496 KiB

sirni

/*
 * tdiiy69
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
 
#define err(N) cerr << #N << " = " << N << '\n';
#define err1(A, N) cerr << #A << " = [";\
	for(int i = 1; i <= N; i++) { cerr << A[i]; if(i < N) cerr << ", "; } cerr << "]\n";
#define err0(A, N) cerr << #A << " = [";\
	for(int i = 0; i < N; i++) { cerr << A[i]; if(i < N - 1) cerr << ", "; } cerr << "]\n";
 
const int INF = 2e9 + 7;
const long long INFLL = 2e18 + 7;
const int N = 1e5 + 5;
const int V = 1e7 + 5;
 
struct DSU { // Disjoint Sets Union
	DSU(int _n) : lab(_n + 5, - 1) {}
 
	int root(int u) {
		return lab[u] < 0 ? u : lab[u] = root(lab[u]);
	}
 
	bool unite(int u, int v) {
		u = root(u); v = root(v);
		if(u == v) return false;
		if(lab[u] > lab[v]) swap(u, v);
		lab[u] += lab[v];
		lab[v] = u;
		return true;
	}
 
	int size(int u) {
		return -lab[root(u)];
	}
 
	private:
	vector<int> lab;
};
 
vector<pair<int, int>> need[V];
int a[N], nxt[V];
 
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	int maxi = 0;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		maxi = max(maxi, a[i]);
	}
	sort(a, a + n);
	n = unique(a, a + n) - a;
	memset(nxt, -1, sizeof nxt);
	for(int i = 0; i < n; i++) {
		nxt[a[i]] = i;
	}
	for(int v = maxi - 1; v >= 0; v--) {
		if(nxt[v] == -1) nxt[v] = nxt[v + 1];
	}
	for(int i = 0; i < n - 1; i++) {
		need[a[i + 1] % a[i]].push_back({i + 1, i});
		for(int j = a[i]; j <= maxi; j += a[i]) {
			need[a[nxt[j]] % a[i]].push_back({nxt[j], i});
		}
	}
	DSU dsu(n);
	long long ans = 0;
	for(int i = 0; i < maxi; i++) {
		for(const auto &[u, v] : need[i]) {
			if(dsu.unite(u, v)) ans += i;
		}
	}
	cout << ans;
	return (0 ^ 0);
}

• 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