Submission #684910

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
684910	2023-01-22T20:07:45 Z	rainboy	Park (JOI17_park)	C++17	100 / 100	413 ms	588 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	10 ms	348 KB	Output is correct
3	Correct	7 ms	340 KB	Output is correct
4	Correct	19 ms	340 KB	Output is correct
5	Correct	34 ms	296 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	405 ms	504 KB	Output is correct
2	Correct	201 ms	504 KB	Output is correct
3	Correct	207 ms	508 KB	Output is correct
4	Correct	393 ms	460 KB	Output is correct
5	Correct	413 ms	500 KB	Output is correct

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	225 ms	340 KB	Output is correct
2	Correct	250 ms	400 KB	Output is correct
3	Correct	255 ms	572 KB	Output is correct
4	Correct	224 ms	448 KB	Output is correct
5	Correct	263 ms	340 KB	Output is correct
6	Correct	240 ms	388 KB	Output is correct
7	Correct	233 ms	400 KB	Output is correct
8	Correct	239 ms	508 KB	Output is correct

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	360 KB	Output is correct
2	Correct	253 ms	440 KB	Output is correct
3	Correct	253 ms	464 KB	Output is correct
4	Correct	254 ms	456 KB	Output is correct
5	Correct	275 ms	460 KB	Output is correct
6	Correct	246 ms	428 KB	Output is correct
7	Correct	306 ms	420 KB	Output is correct
8	Correct	257 ms	548 KB	Output is correct
9	Correct	267 ms	524 KB	Output is correct
10	Correct	252 ms	400 KB	Output is correct
11	Correct	251 ms	588 KB	Output is correct
12	Correct	279 ms	456 KB	Output is correct
13	Correct	263 ms	448 KB	Output is correct
14	Correct	249 ms	408 KB	Output is correct
15	Correct	281 ms	520 KB	Output is correct
16	Correct	235 ms	416 KB	Output is correct
17	Correct	408 ms	504 KB	Output is correct
18	Correct	259 ms	468 KB	Output is correct
19	Correct	309 ms	420 KB	Output is correct
20	Correct	277 ms	520 KB	Output is correct

Subtask #5

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	287 ms	456 KB	Output is correct
2	Correct	302 ms	484 KB	Output is correct
3	Correct	256 ms	404 KB	Output is correct
4	Correct	242 ms	464 KB	Output is correct
5	Correct	294 ms	536 KB	Output is correct
6	Correct	246 ms	504 KB	Output is correct
7	Correct	303 ms	436 KB	Output is correct
8	Correct	241 ms	440 KB	Output is correct
9	Correct	252 ms	420 KB	Output is correct
10	Correct	240 ms	468 KB	Output is correct
11	Correct	241 ms	420 KB	Output is correct
12	Correct	286 ms	428 KB	Output is correct
13	Correct	250 ms	392 KB	Output is correct
14	Correct	292 ms	520 KB	Output is correct
15	Correct	250 ms	484 KB	Output is correct
16	Correct	232 ms	388 KB	Output is correct
17	Correct	398 ms	504 KB	Output is correct
18	Correct	258 ms	404 KB	Output is correct