Submission #704536

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
704536	2023-03-02T09:06:30 Z	SamNguyen	ICC (CEOI16_icc)	C++14	40 / 100	220 ms	596 KB

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

class DSU {
private:
	int n;
	vector<int> sz, par;

public:
	DSU(int n = 0): n(n) {
		sz.assign(n + 1, 1);
		par.assign(n + 1, 0);
		iota(par.begin(), par.end(), 0);
	}

	int root(int u) { return par[u] = (u == par[u] ? u : root(par[u])); }

	bool join(int u, int v) {
		u = root(u), v = root(v);
		if (u == v)
			return false;

		if (sz[u] < sz[v])
			swap(u, v);
		sz[u] += sz[v];
		par[v] = u;
		return true;
	}

	inline bool is_same(int u, int v) {
		return root(u) == root(v);
	}

	vector<int> get_roots() {
		vector<int> res;
		for (int i = 1; i <= n; i++) if (root(i) == i)
			res.push_back(i);
		return res;
	}
};

int buffer[2][200];
int query(vector<int> a, vector<int> b) {
	if (a.empty() or b.empty())
		return false;

	copy(a.begin(), a.end(), buffer[0]);
	copy(b.begin(), b.end(), buffer[1]);
	return query(a.size(), b.size(), buffer[0], buffer[1]);
}

pair<vector<int>, vector<int>> divide_halves(const vector<int> &X) {
	vector<int> L, R;
	int m = int(X.size()) / 2;

	for (int i = 0; i < m; i++)
		L.push_back(X[i]);
	for (int i = m; i < int(X.size()); i++)
		R.push_back(X[i]);
	return make_pair(L, R);
}

mt19937 rnd(20050701 + time(NULL));
DSU dsu;
vector<vector<int>> comps;

int query_cc(vector<int> L, vector<int> R) {
	vector<int> X, Y;
	for (int x : L)
		copy(comps[x].begin(), comps[x].end(), back_inserter(X));
	for (int y : R)
		copy(comps[y].begin(), comps[y].end(), back_inserter(Y));

	return query(X, Y);
}

void find_root_edge_2(vector<int> L, vector<int> R) {
	if (L.size() == 1 and R.size() == 1)
		throw make_pair(L.front(), R.front());

	if (L.size() < R.size())
		swap(L, R);

	vector<int> L1, L2;
	tie(L1, L2) = divide_halves(L);

	if (query_cc(L1, R))
		return find_root_edge_2(L1, R);
	return find_root_edge_2(L2, R);
}

void find_edge_2(vector<int> L, vector<int> R) {
	if (L.size() == 1 and R.size() == 1)
		throw make_pair(L.front(), R.front());

	if (L.size() < R.size())
		swap(L, R);

	vector<int> L1, L2;
	tie(L1, L2) = divide_halves(L);

	if (query(L1, R))
		return find_edge_2(L1, R);
	return find_edge_2(L2, R);
}

void find_root_edge(vector<int> X) {
	while (true) {
		vector<int> L, R;
		for (int e : X) {
			if (rnd() & 1)
				L.push_back(e);
			else
				R.push_back(e);
		}

		if (query_cc(L, R)) 
			find_root_edge_2(L, R);
	}
}

void run(int N) {
	dsu = DSU(N);
	for (int t = N - 1; t--; ) {
		vector<int> roots = dsu.get_roots();

		comps.assign(N + 1, {});
		for (int r : roots) 
			for (int i = 1; i <= N; i++) if (dsu.root(i) == r)
				comps[r].push_back(i);
		
		try {
			find_root_edge(roots);
		} 
		catch (pair<int, int> e) {
			int x, y;
			tie(x, y) = e;

			try {
				find_edge_2(comps[x], comps[y]);
			}
			catch (pair<int, int> e) {
				int u, v;
				tie(u, v) = e;
				setRoad(u, v);
				dsu.join(u, v);
				continue;
			}

			cout << "Program failed.";
			exit(-1);
		}

		cout << "Program failed.";
		exit(-1);
	}
}

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	468 KB	Ok! 125 queries used.
2	Correct	8 ms	568 KB	Ok! 121 queries used.

Subtask #2
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	564 KB	Ok! 666 queries used.
2	Correct	60 ms	564 KB	Ok! 877 queries used.
3	Correct	55 ms	568 KB	Ok! 854 queries used.

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	576 KB	Ok! 1851 queries used.
2	Correct	220 ms	576 KB	Ok! 2137 queries used.
3	Correct	172 ms	576 KB	Ok! 2080 queries used.
4	Correct	163 ms	576 KB	Ok! 1995 queries used.