Submission #684910

#	Time	Username	Problem	Language	Result	Execution time	Memory
684910		rainboy	Park (JOI17_park)	C++17	100 / 100	413 ms	588 KiB

park

/* https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d3-natural_park-review.pdf */
#include "park.h"
#include <stdlib.h>
#include <string.h>

const int N = 1400;

int *ej[N], eo[N], n;

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int ask(int i, int j, int *used) {
	int tmp;
	if (i > j)
		tmp = i, i = j, j = tmp;
	used[i] = used[j] = 1;
	return Ask(i, j, used);
}

void answer(int i, int j) {
	int tmp;
	if (i > j)
		tmp = i, i = j, j = tmp;
	Answer(i, j);
	append(i, j), append(j, i);
}

int query(int *ii, int k, int j, int type) {
	static int used[N];
	for (int i = 0; i < n; i++)
		used[i] = type ^ 1;
	for (int h = 0; h < k; h++)
		used[ii[h]] = type;
	return ask(type == 0 ? 0 : ii[0], j, used);
}

char visited[N]; int qu[N], cnt;

void dfs(int i) {
	if (visited[i])
		return;
	visited[i] = 1, qu[cnt++] = i;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		dfs(j);
	}
}

void search(int *ii, int k, int j) {
	while (k > 0) {
		for (int i = 0; i < n; i++)
			visited[i] = 1;
		for (int h = 0; h < k; h++)
			visited[ii[h]] = 0;
		cnt = 0, dfs(ii[0]);
		if (query(qu, cnt, j, 1)) {
			int lower = -1, upper = cnt - 1;
			while (upper - lower > 1) {
				int h = (lower + upper) / 2;
				if (query(qu, h + 1, j, 1))
					upper = h;
				else
					lower = h;
			}
			int i = qu[upper];
			answer(i, j);
			for (int h = 0; h < k; h++)
				if (ii[h] == i) {
					while (h + 1 < k)
						ii[h] = ii[h + 1], h++;
					ii[h] = i;
					break;
				}
			k--;
		} else {
			int tmp;
			for (int h = 0, h_ = 0; h < k; h++)
				if (!visited[ii[h]])
					tmp = ii[h_], ii[h_] = ii[h], ii[h] = tmp, h_++;
			k -= cnt;
		}
	}
}

void Detect(int t_, int n_) {
	static int ii[N];
	n = n_;
	for (int j = 0; j < n; j++) {
		int lower = 0, upper = j;
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;
			if (query(ii + h, j - h, j, 0))
				upper = h;
			else
				lower = h;
		}
		for (int h = j; h > upper; h--)
			ii[h] = ii[h - 1];
		ii[upper] = j;
	}
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int h = 1; h < n; h++)
		search(ii, h, ii[h]);
	for (int i = 0; i < n; i++)
		free(ej[i]);
}

Compilation message (stderr)

park.cpp: In function 'void append(int, int)':
park.cpp:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23