oj.uz

답안 #704522

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704522 2023-03-02T08:58:17 Z SamNguyen CEOI16_icc (CEOI16_icc) C++14
18 / 100
 213 ms 572 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());

	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) {
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 468 KB Ok! 149 queries used.
2 Correct 10 ms 572 KB Ok! 148 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 556 KB Ok! 814 queries used.
2 Correct 64 ms 560 KB Ok! 964 queries used.
3 Correct 81 ms 560 KB Ok! 918 queries used.

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 468 KB Ok! 2185 queries used.
2 Incorrect 213 ms 568 KB Too many queries! 2338 out of 2250
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 178 ms 564 KB Too many queries! 2240 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 203 ms 564 KB Too many queries! 2371 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 208 ms 564 KB Too many queries! 2334 out of 1625
2 Halted 0 ms 0 KB -