Submission #171553

#	Time	Username	Problem	Language	Result	Execution time	Memory
171553		maruii	Park (JOI17_park)	C++14	10 / 100	37 ms	504 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;

static int Place[1400];

vector<int> edge[1400];
int dfn[1401], idfn[1401], dfnn;
void dfs(int x, int p) {
	dfn[x] = ++dfnn;
	idfn[dfnn] = x;
	for (auto i : edge[x])
		if (i != p) dfs(i, x);
}

bool f(int m, int x) {
	if (m > x) return 0;
	memset(Place, 0, sizeof(Place));
	Place[0] = Place[x] = 1;
	for (int i = 1; i <= m; ++i) Place[idfn[i]] = 1;
	return Ask(0, x, Place);
}

void Detect(int T, int N) {
	if (T == 1) {
		for (int i = 0; i < N; ++i) {
			for (int j = i + 1; j < N; ++j) {
				memset(Place, 0, 4 * N);
				Place[i] = Place[j] = 1;
				if (Ask(i, j, Place)) Answer(i, j);
			}
		}
		return;
	}
	if (T < 5) {
		for (int i = 1; i < N; ++i) {
			dfnn = 0;
			dfs(0, 0);
			int l = 1, r = i + 1;
			while (l < r) {
				int m = l + r >> 1;
				if (f(m, i)) r = m;
				else l = m + 1;
			}
			if (l <= i) {
				edge[idfn[l]].push_back(i);
				edge[i].push_back(idfn[l]);
				Answer(min(idfn[l], i), max(idfn[l], i));
			}
		}
		return;
	}
}

Compilation message (stderr)

park.cpp: In function 'void Detect(int, int)':
park.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~

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