Submission #1041361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041361		sssamui	Sirni (COCI17_sirni)	C++17	140 / 140	985 ms	750232 KiB

sirni

#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 / 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