oj.uz

Submission #1041310

# Submission time Handle Problem Language Result Execution time Memory
1041310 2024-08-01T20:59:30 Z sssamui Sirni (COCI17_sirni) C++17
98 / 140
 5000 ms 405648 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
using ll = long long;

const ll one = 1;

vector<int> p(1e5);

int rt(int node)
{
	if (p[node] == node) return node;
	return p[node] = rt(p[node]);
}

void join(int a, int b)
{
	p[rt(a)] = rt(b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	set<int> ps;
	while (n--)
	{
		int p;
		cin >> p;
		ps.insert(p);
	}

	vector<int> plst(0);
	for (int p : ps) plst.push_back(p);
	n = plst.size();
	for (int i = 0; i < n; i++) p[i] = i;

	map<int, int> inv;
	for (int i = 0; i < n; i++) inv[plst[i]] = i;

	vector<pair<int, pair<int, int>>> edg(0);
	for (int p : ps)
	{
		auto it = ps.upper_bound(p);
		while (it != ps.end())
		{
			int chk = *it;
			edg.push_back({ chk % p, {inv[p], inv[chk]} });
			chk += p;
			chk /= p;
			chk *= p;
			it = ps.lower_bound(chk);
		}
	}

	sort(edg.begin(), edg.end());
	ll ans = 0;
	for (pair<int, pair<int, int>> nxt : edg) if (rt(nxt.second.first) != rt(nxt.second.second))
	{
		ans += one * nxt.first;
		join(nxt.second.first, nxt.second.second);
	}

	cout << ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 26 ms 4052 KB Output is correct
3 Correct 3 ms 1116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 8 ms 1748 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 25404 KB Output is correct
2 Correct 1413 ms 60972 KB Output is correct
3 Correct 510 ms 34480 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 5316 KB Output is correct
2 Correct 411 ms 51924 KB Output is correct
3 Correct 386 ms 22028 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 62336 KB Output is correct
2 Correct 1928 ms 109244 KB Output is correct
3 Correct 547 ms 36148 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 11308 KB Output is correct
2 Correct 1521 ms 107300 KB Output is correct
3 Correct 458 ms 34864 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 37684 KB Output is correct
2 Execution timed out 5022 ms 405648 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 36400 KB Output is correct
2 Execution timed out 5068 ms 403816 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 6084 KB Output is correct
2 Execution timed out 5082 ms 402808 KB Time limit exceeded
3 Halted 0 ms 0 KB -