oj.uz

Submission #1018424

# Submission time Handle Problem Language Result Execution time Memory
1018424 2024-07-10T03:43:29 Z GentleRage Sirni (COCI17_sirni) C++17
84 / 140
 706 ms 786432 KB 
/*
 * tdiiy69
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define int long long
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);
	int 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 131 ms 314452 KB Output is correct
2 Correct 195 ms 371284 KB Output is correct
3 Correct 136 ms 314880 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 314452 KB Output is correct
2 Runtime error 594 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 314372 KB Output is correct
2 Correct 130 ms 314192 KB Output is correct
3 Correct 165 ms 314452 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 335852 KB Output is correct
2 Correct 215 ms 392048 KB Output is correct
3 Correct 183 ms 360976 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 318556 KB Output is correct
2 Correct 174 ms 359116 KB Output is correct
3 Correct 159 ms 336064 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 361148 KB Output is correct
2 Correct 244 ms 428008 KB Output is correct
3 Correct 166 ms 353940 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 321936 KB Output is correct
2 Correct 247 ms 427324 KB Output is correct
3 Correct 163 ms 356388 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 341388 KB Output is correct
2 Runtime error 569 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 350724 KB Output is correct
2 Runtime error 662 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 319180 KB Output is correct
2 Runtime error 706 ms 786432 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -