oj.uz

Submission #704516

# Submission time Handle Problem Language Result Execution time Memory
704516 2023-03-02T08:38:27 Z SamNguyen ICC (CEOI16_icc) C++14
18 / 100
 295 ms 580 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);
}

namespace subtask_1 {
	void run(int N) {
		DSU dsu(N);
		for (int t = N - 1; t--; ) {
			[&]() {
				for (int u = 1; u <= N; u++)
				for (int v = u + 1; v <= N; v++) {
					if (not dsu.is_same(u, v) and query({u}, {v})) {
						setRoad(u, v);
						dsu.join(u, v);
						return;
					}
				}
			}();
		}
	}
}

namespace subtask_2 {
	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());

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

		if (query_cc(L1, R1))
			return find_root_edge_2(L1, R1);
		if (query_cc(L1, R2))
			return find_root_edge_2(L1, R2);
		if (query_cc(L2, R1))
			return find_root_edge_2(L2, R1);
		return find_root_edge_2(L2, R2);
	}

	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());

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

		if (query(L1, R1))
			return find_edge_2(L1, R1);
		if (query(L1, R2))
			return find_edge_2(L1, R2);
		if (query(L2, R1))
			return find_edge_2(L2, R1);
		return find_edge_2(L2, R2);
	}

	void find_root_edge(vector<int> X) {
		if (X.size() <= 1)
			return;

		vector<int> L, R;
		tie(L, R) = divide_halves(X);

		if (not query_cc(L, R)) {
			find_root_edge(L);
			find_root_edge(R);
			return;
		}

		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);
		}
	}
}

void run(int N) {
	subtask_2::run(N);
	return;

	if (N == 15)
		subtask_1::run(N);
	if (N == 50)
		subtask_2::run(N);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB Ok! 136 queries used.
2 Correct 8 ms 468 KB Ok! 139 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 556 KB Ok! 1118 queries used.
2 Correct 74 ms 552 KB Ok! 1452 queries used.
3 Correct 75 ms 552 KB Ok! 1456 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 564 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 580 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 233 ms 564 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 212 ms 468 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -