oj.uz

Submission #86230

# Submission time Handle Problem Language Result Execution time Memory
86230 2018-11-25T14:09:31 Z JustInCase ICC (CEOI16_icc) C++17
100 / 100
 173 ms 936 KB 
#include <bits/stdc++.h>
#include <icc.h>

#define Run run
#define Query query
#define SetRoad setRoad
#define int32_t int

const int32_t MAX_N = 100;

int32_t parent[MAX_N + 5], size[MAX_N + 5];

int32_t FindParent(int32_t x) {
	if(parent[x] == x) {
		return x;
	}
	else {
		parent[x] = FindParent(parent[x]);
		return parent[x];
	}
}

void Unite(int32_t x, int32_t y) {
	int32_t parX = FindParent(x);
	int32_t parY = FindParent(y);

	if(parX == parY) {
		return;
	}

	if(size[parX] <= size[parY]) {
		parent[parX] = parY;
		size[parY] += size[parX];
	}
	else {
		parent[parY] = parX;
		size[parX] += size[parY];
	}
}

int32_t Query(int32_t sizeA, int32_t sizeB, int32_t *a, int32_t *b);

void SetRoad(int32_t a, int32_t b);

void Run(int32_t n) {
	for(int32_t i = 1; i <= n; i++) {
		parent[i] = i;
		size[i] = 1;
	}
	
	bool isBitDiff[10];
	int32_t sizeA, sizeB, a[MAX_N + 5], b[MAX_N + 5];
	int32_t compInd[MAX_N + 5];

	for(int32_t q = 0; q < n - 1; q++) {	
		int32_t cntComps = 0;
		for(int32_t i = 1; i <= n; i++) {
			if(parent[i] == i) {
				compInd[i - 1] = cntComps;
				cntComps++;
			}
		}

		std::vector< int32_t > comps[MAX_N + 5];
		for(int32_t i = 0; i < n; i++) {
			comps[compInd[FindParent(i + 1) - 1]].push_back(i);
		}

		memset(isBitDiff, 0, sizeof(isBitDiff));
		int32_t comp1 = -1;
		for(int32_t j = 0; (1 << j) < cntComps; j++) {
			sizeA = 0;
			sizeB = 0;
			
			std::vector< int32_t > aComps;
			for(int32_t p = 0; p < cntComps; p++) {
				if((p & (1 << j)) == 0) {
					aComps.push_back(p);
					for(auto &x : comps[p]) {
						a[sizeA] = x + 1;
						sizeA++;
					}
				}
				else {
					for(auto &x : comps[p]) {
						b[sizeB] = x + 1;
						sizeB++;
					}
				}
			}

			if(Query(sizeA, sizeB, a, b) == 1) {
				isBitDiff[j] = true;
				
				if(comp1 == -1) {
					int32_t low = 0, high = aComps.size() - 1;
					while(low <= high) {
						if(low == high) {
							comp1 = aComps[low];
							break;
						}
						
						int32_t mid = (low + high) / 2;
							
						sizeA = 0;
						for(int32_t i = low; i <= mid; i++) {
							for(auto &x : comps[aComps[i]]) {
								a[sizeA] = x + 1;
								sizeA++;
							}
						}

						if(Query(sizeA, sizeB, a, b) == 1) {
							high = mid;
						}
						else {
							low = mid + 1;
						}
					}
				}
			}
		}
		
		int32_t comp2 = comp1;
		for(int32_t i = 0; (1 << i) < cntComps; i++) {
			if(isBitDiff[i]) {
				comp2 ^= (1 << i);
			}
		}

		sizeB = 0;
		for(auto &x : comps[comp2]) {
			b[sizeB] = x + 1;
			sizeB++;
		}
	
		int32_t u = -1;
		int32_t low = 0, high = comps[comp1].size() - 1;
		while(low <= high) {
			if(low == high) {
				u = comps[comp1][low];
				break;
			}

			int32_t mid = (low + high) / 2;

			sizeA = 0;
			for(int32_t i = low; i <= mid; i++) {
				a[sizeA] = comps[comp1][i] + 1;
				sizeA++;
			}

			if(Query(sizeA, sizeB, a, b) == 1) {
				high = mid;
			}
			else {
				low = mid + 1;
			}
		}

		a[0] = u + 1;
		sizeA = 1;
		
		int32_t v = -1;
		low = 0;
		high = comps[comp2].size() - 1;
		while(low <= high) {
			if(low == high) {
				v = comps[comp2][low];
				break;
			}

			int32_t mid = (low + high) / 2;		
		
			sizeB = 0;
			for(int32_t i = low; i <= mid; i++) {
				b[sizeB] = comps[comp2][i] + 1;
				sizeB++;
			}

			if(Query(sizeA, sizeB, a, b) == 1) {
				high = mid;
			}
			else {
				low = mid + 1;
			}
		}
		
		Unite(u + 1, v + 1);
		SetRoad(u + 1, v + 1);
	}
}

/**
void SetRoad(int32_t a, int32_t b) {
	std::cout << "The new road is: " << a << " " << b << '\n';
}

int32_t Query(int32_t sizeA, int32_t sizeB, int32_t *a, int32_t *b) {
	std::cout << '\n' << "QUERY" << '\n';

	std::cout << "A: ";
	for(int32_t i = 0; i < sizeA; i++) {
		std::cout << a[i] << " ";
	}
	std::cout << '\n' << "B: ";
	for(int32_t i = 0; i < sizeB; i++) {
		std::cout << b[i] << " ";
	}
	std::cout << '\n';

	int32_t res;
	std::cin >> res;

	return res;
}

int main() {
	Run(4);	
}
*/

#undef Run
#undef Query
#undef int32_t

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Ok! 113 queries used.
2 Correct 10 ms 628 KB Ok! 112 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 628 KB Ok! 632 queries used.
2 Correct 47 ms 724 KB Ok! 597 queries used.
3 Correct 47 ms 724 KB Ok! 623 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 732 KB Ok! 1544 queries used.
2 Correct 148 ms 732 KB Ok! 1556 queries used.
3 Correct 162 ms 736 KB Ok! 1587 queries used.
4 Correct 145 ms 752 KB Ok! 1530 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 752 KB Ok! 1559 queries used.
2 Correct 173 ms 752 KB Ok! 1559 queries used.
3 Correct 162 ms 756 KB Ok! 1578 queries used.
4 Correct 158 ms 820 KB Ok! 1562 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 820 KB Ok! 1544 queries used.
2 Correct 154 ms 836 KB Ok! 1547 queries used.
3 Correct 152 ms 840 KB Ok! 1578 queries used.
4 Correct 154 ms 860 KB Ok! 1575 queries used.
5 Correct 154 ms 860 KB Ok! 1551 queries used.
6 Correct 148 ms 860 KB Ok! 1576 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 936 KB Ok! 1578 queries used.
2 Correct 151 ms 936 KB Ok! 1556 queries used.