Submission #1041310

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041310		sssamui	Sirni (COCI17_sirni)	C++17	98 / 140	5082 ms	405648 KiB

sirni

#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 / 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: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14