oj.uz

Submission #86232

# Submission time Handle Problem Language Result Execution time Memory
86232 2018-11-25T14:10:25 Z JustInCase ICC (CEOI16_icc) C++17
100 / 100
 169 ms 940 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];
	}
}

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

#undef Run
#undef Query
#undef int32_t

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 592 KB Ok! 113 queries used.
2 Correct 11 ms 640 KB Ok! 112 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 640 KB Ok! 632 queries used.
2 Correct 49 ms 640 KB Ok! 597 queries used.
3 Correct 52 ms 640 KB Ok! 623 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 684 KB Ok! 1544 queries used.
2 Correct 169 ms 756 KB Ok! 1556 queries used.
3 Correct 154 ms 756 KB Ok! 1587 queries used.
4 Correct 158 ms 876 KB Ok! 1530 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 876 KB Ok! 1559 queries used.
2 Correct 158 ms 920 KB Ok! 1559 queries used.
3 Correct 152 ms 920 KB Ok! 1578 queries used.
4 Correct 164 ms 920 KB Ok! 1562 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 920 KB Ok! 1544 queries used.
2 Correct 154 ms 920 KB Ok! 1547 queries used.
3 Correct 158 ms 920 KB Ok! 1578 queries used.
4 Correct 152 ms 936 KB Ok! 1575 queries used.
5 Correct 145 ms 940 KB Ok! 1551 queries used.
6 Correct 144 ms 940 KB Ok! 1576 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 940 KB Ok! 1578 queries used.
2 Correct 145 ms 940 KB Ok! 1556 queries used.