oj.uz

Submission #1041361

# Submission time Handle Problem Language Result Execution time Memory
1041361 2024-08-01T23:11:05 Z sssamui Sirni (COCI17_sirni) C++17
140 / 140
 985 ms 750232 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

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> fps(0);
	for (int p : ps) fps.push_back(p);
	n = fps.size();
	for (int i = 0; i < n; i++) p[i] = i;

	int lgst = fps.back();
	vector<int> nxtlg(lgst + 1, -1);
	for (int i = 0; i < n; i++) nxtlg[fps[i]] = i;
	for (int i = lgst - 1; i > -1; i--) if (nxtlg[i] == -1) nxtlg[i] = nxtlg[i + 1];

	vector<vector<pair<int, int>>> edg(lgst + 1);
	for (int i = 0; i < n - 1; i++)
	{
		edg[fps[i + 1] % fps[i]].push_back({ i, i + 1 });
		for (int np = 2 * fps[i]; np <= lgst; np += fps[i])
		{
			int nxt = nxtlg[np];
			edg[fps[nxt] % fps[i]].push_back({ i, nxt });
		}
	}

	int ans = 0;
	for (int i = 0; i <= lgst; i++) for (pair<int, int> eg : edg[i]) if (rt(eg.first) != rt(eg.second))
	{
		ans += i;
		join(eg.first, eg.second);
	}

	cout << ans;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 274776 KB Output is correct
2 Correct 144 ms 303024 KB Output is correct
3 Correct 98 ms 274008 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 662 ms 668756 KB Output is correct
3 Correct 107 ms 275540 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 274656 KB Output is correct
2 Correct 96 ms 274260 KB Output is correct
3 Correct 102 ms 274968 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 42684 KB Output is correct
2 Correct 107 ms 73200 KB Output is correct
3 Correct 71 ms 53276 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 30812 KB Output is correct
2 Correct 51 ms 51324 KB Output is correct
3 Correct 49 ms 28344 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 54672 KB Output is correct
2 Correct 112 ms 93536 KB Output is correct
3 Correct 64 ms 52924 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 11396 KB Output is correct
2 Correct 117 ms 89164 KB Output is correct
3 Correct 67 ms 56252 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 292552 KB Output is correct
2 Correct 720 ms 638068 KB Output is correct
3 Correct 168 ms 296316 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 297412 KB Output is correct
2 Correct 985 ms 750232 KB Output is correct
3 Correct 246 ms 352560 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 277844 KB Output is correct
2 Correct 827 ms 637836 KB Output is correct
3 Correct 69 ms 58044 KB Output is correct