제출 #1144116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144116		tleSquared	Sirni (COCI17_sirni)	C++20	0 / 140	241 ms	292876 KiB

sirni

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

vector<int> parent, ranks;

class DisjointSets {
  private:
	vector<int> parents;
	vector<int> sizes;

  public:
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}

	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }

	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }

		if (sizes[x_root] < sizes[y_root]) { std::swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}

	bool connected(int x, int y) { return find(x) == find(y); }
};

int main()
{
    ll n;
	cin >> n;
	vector<ll> cards(n);
	for (int i = 0; i < n; i++) cin >> cards[i];

    sort(cards.begin(), cards.end());

    cards.erase(unique(cards.begin(), cards.end()), cards.end());

    ll maxi = cards.back();
    vector<int> next_largest(maxi+1);
    ll ind = 0, cur = -1;
    for (int i = 0; i <= maxi; i++)
    {
        if (i == cards[ind])
        {
            ind++;
            cur = ind;
        }
        next_largest[i] = cur;
    }

    vector<vector<pair<int, int> > > edges(maxi + 1);
	for (int i = 0; i < cards.size() - 1; i++)
    {
		edges[cards[i + 1] % cards[i]].push_back(make_pair(i, i + 1));
		for (int mul = 2 * cards[i]; mul <= maxi; mul += cards[i])
        {
			edges[cards[next_largest[mul]] % cards[i]].push_back(make_pair(i, next_largest[mul]));
		}
	}

    ll cost = 0;
	DisjointSets lcards(cards.size());
	for (int c = 0; c <= maxi; c++)
    {
		for (pair<int, int> edge : edges[c])
        {
			if (lcards.unite(edge.first, edge.second)) cost += c;
		}
	}

	cout << cost << endl;

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14