oj.uz

Submission #704573

# Submission time Handle Problem Language Result Execution time Memory
704573 2023-03-02T10:06:54 Z SamNguyen ICC (CEOI16_icc) C++14
100 / 100
 180 ms 888 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) {
	set<pair<int, int>> possibles;

	for (int x1 : X)
	for (int x2 : X) if (x1 < x2)
		possibles.emplace(x1, x2);

	while (possibles.size() > 1) {
		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)) {
			for (int x1 : L)
			for (int x2 : L) if (x1 < x2)
				possibles.erase(make_pair(x1, x2));

			for (int x1 : R)
			for (int x2 : R) if (x1 < x2)
				possibles.erase(make_pair(x1, x2));
		}
		else {
			for (int x1 : L)
			for (int x2 : R) 
				possibles.erase(minmax(x1, x2));
		}
	}

	throw *possibles.begin();
}

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 7 ms 468 KB Ok! 127 queries used.
2 Correct 8 ms 564 KB Ok! 122 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 596 KB Ok! 720 queries used.
2 Correct 37 ms 596 KB Ok! 533 queries used.
3 Correct 42 ms 692 KB Ok! 581 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 760 KB Ok! 1633 queries used.
2 Correct 167 ms 724 KB Ok! 1322 queries used.
3 Correct 173 ms 748 KB Ok! 1653 queries used.
4 Correct 176 ms 888 KB Ok! 1577 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 724 KB Ok! 1637 queries used.
2 Correct 174 ms 768 KB Ok! 1585 queries used.
3 Correct 176 ms 724 KB Ok! 1525 queries used.
4 Correct 178 ms 724 KB Ok! 1680 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 744 KB Ok! 1480 queries used.
2 Correct 169 ms 724 KB Ok! 1465 queries used.
3 Correct 172 ms 888 KB Ok! 1456 queries used.
4 Correct 175 ms 768 KB Ok! 1568 queries used.
5 Correct 180 ms 724 KB Ok! 1698 queries used.
6 Correct 178 ms 768 KB Ok! 1572 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 772 KB Ok! 1460 queries used.
2 Correct 169 ms 760 KB Ok! 1430 queries used.