oj.uz

Submission #545902

# Submission time Handle Problem Language Result Execution time Memory
545902 2022-04-05T16:05:28 Z rainboy ICC (CEOI16_icc) C++
100 / 100
 129 ms 496 KB 
#include "icc.h"
#include <string.h>

#define N	100

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

void run(int n) {
	static int cc[N], ii1[N], ii2[N];
	int h;

	memset(ds, -1, n * sizeof *ds);
	for (h = 0; h < n - 1; h++) {
		int n1, n2, i, j, l, l_, c, c1, c2, lower, upper;

		for (i = 0, c = 0; i < n; i++)
			if (ds[i] < 0)
				cc[i] = c++;
		for (i = 0; i < n; i++)
			cc[i] = cc[find(i)];
		c2 = 0, l_ = -1;
		for (l = 0; (1 << l) < c; l++) {
			n1 = 0, n2 = 0;
			for (i = 0; i < n; i++)
				if ((cc[i] & 1 << l) == 0)
					ii1[n1++] = i + 1;
				else
					ii2[n2++] = i + 1;
			if (n1 != 0 && n2 != 0 && query(n1, n2, ii1, ii2))
				c2 |= 1 << l, l_ = l;
		}
		c1 = 0;
		for (l = 0; (1 << l) < c; l++) {
			if (l == l_)
				continue;
			n1 = 0, n2 = 0;
			for (i = 0; i < n; i++)
				if ((cc[i] & ((1 << l) | (1 << l_))) == 0)
					ii1[n1++] = i + 1;
				else
					ii2[n2++] = i + 1;
			if (n1 == 0 || n2 == 0 || !query(n1, n2, ii1, ii2))
				c1 |= 1 << l;
		}
		c2 ^= c1;
		n1 = 0, n2 = 0;
		for (i = 0; i < n; i++)
			if (cc[i] == c1)
				ii1[n1++] = i + 1;
			else if (cc[i] == c2)
				ii2[n2++] = i + 1;
		lower = 0, upper = n1;
		while (upper - lower > 1) {
			int g = (lower + upper) / 2;

			if (query(g - lower, n2, ii1 + lower, ii2))
				upper = g;
			else
				lower = g;
		}
		i = ii1[lower] - 1;
		lower = 0, upper = n2;
		while (upper - lower > 1) {
			int g = (lower + upper) / 2;

			if (query(n1, g - lower, ii1, ii2 + lower))
				upper = g;
			else
				lower = g;
		}
		j = ii2[lower] - 1;
		setRoad(i + 1, j + 1), join(i, j);
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Ok! 117 queries used.
2 Correct 6 ms 468 KB Ok! 116 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 468 KB Ok! 651 queries used.
2 Correct 34 ms 468 KB Ok! 585 queries used.
3 Correct 33 ms 468 KB Ok! 656 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 488 KB Ok! 1607 queries used.
2 Correct 110 ms 476 KB Ok! 1398 queries used.
3 Correct 112 ms 476 KB Ok! 1613 queries used.
4 Correct 116 ms 480 KB Ok! 1611 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 480 KB Ok! 1595 queries used.
2 Correct 119 ms 480 KB Ok! 1561 queries used.
3 Correct 112 ms 468 KB Ok! 1613 queries used.
4 Correct 118 ms 480 KB Ok! 1611 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 496 KB Ok! 1581 queries used.
2 Correct 121 ms 484 KB Ok! 1613 queries used.
3 Correct 117 ms 468 KB Ok! 1556 queries used.
4 Correct 112 ms 492 KB Ok! 1613 queries used.
5 Correct 123 ms 484 KB Ok! 1588 queries used.
6 Correct 120 ms 468 KB Ok! 1611 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 468 KB Ok! 1613 queries used.
2 Correct 114 ms 468 KB Ok! 1613 queries used.