oj.uz

Submission #1018427

# Submission time Handle Problem Language Result Execution time Memory
1018427 2024-07-10T03:51:04 Z GentleRage Sirni (COCI17_sirni) C++17
140 / 140
 1006 ms 747496 KB 
/*
 * 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 274808 KB Output is correct
2 Correct 165 ms 304212 KB Output is correct
3 Correct 113 ms 275024 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 274768 KB Output is correct
2 Correct 732 ms 669444 KB Output is correct
3 Correct 116 ms 275472 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 274872 KB Output is correct
2 Correct 114 ms 274648 KB Output is correct
3 Correct 113 ms 274768 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 285320 KB Output is correct
2 Correct 188 ms 313344 KB Output is correct
3 Correct 143 ms 297792 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 276944 KB Output is correct
2 Correct 144 ms 297788 KB Output is correct
3 Correct 117 ms 285312 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 297816 KB Output is correct
2 Correct 197 ms 330688 KB Output is correct
3 Correct 150 ms 293964 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 278348 KB Output is correct
2 Correct 196 ms 331376 KB Output is correct
3 Correct 140 ms 295740 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 288708 KB Output is correct
2 Correct 734 ms 634000 KB Output is correct
3 Correct 159 ms 292120 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 293136 KB Output is correct
2 Correct 1006 ms 747496 KB Output is correct
3 Correct 265 ms 348560 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 277200 KB Output is correct
2 Correct 803 ms 635096 KB Output is correct
3 Correct 151 ms 299832 KB Output is correct