Submission #95857

#	Time	Username	Problem	Language	Result	Execution time	Memory
95857		diamond_duke	Park (JOI17_park)	C++11	100 / 100	388 ms	804 KiB

park

#include "park.h"
#include <algorithm>
#include <vector>
int can_go[2005], vis[2005], seq[2005], cnt, n;
bool in[2005], rem[2005];
std::vector<int> adj[2005];
inline void add_edge(int u, int v)
{
	if (u > v)
		std::swap(u, v);
	Answer(u, v);
	adj[u].push_back(v);
	adj[v].push_back(u);
}
inline bool query(int s, int t)
{
	if (s > t)
		std::swap(s, t);
	return Ask(s, t, can_go);
}
bool direct(int u)
{
	for (int i = 0; i < n; i++)
		can_go[i] = vis[i] == 1;
	can_go[u] = true;
	return query(0, u);
}
int get_nxt(int u)
{
	int l = 0, r = n - 1, res = -1;
	while (l <= r)
	{
		int m = l + r >> 1;
		for (int i = 0; i <= m; i++)
			can_go[i] = vis[i] != 2;
		for (int i = m + 1; i < n; i++)
			can_go[i] = vis[i] == 1;
		can_go[u] = true;
		if (query(0, u))
		{
			res = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}
	return res;
}
void clear(int u)
{
	rem[u] = false;
	for (int v : adj[u])
	{
		if (rem[v])
			clear(v);
	}
}
void dfs(int u)
{
	seq[cnt++] = u;
	in[u] = true;
	for (int v : adj[u])
	{
		if (rem[v] && !in[v])
			dfs(v);
	}
}
void find_edge(int u)
{
	for (int i = 0; i < n; i++)
		rem[i] = vis[i] == 1;
	for (int rt = 0; rt < n; rt++)
	{
		while (rem[rt])
		{
			for (int i = 0; i < n; i++)
				can_go[i] = rem[i];
			can_go[u] = 1;
			if (!query(u, rt))
			{
				clear(rt);
				continue;
			}
			cnt = 0;
			for (int i = 0; i < n; i++)
				in[i] = false;
			dfs(rt);
			int l = 0, r = cnt - 1, res = -1;
			while (l <= r)
			{
				int m = l + r >> 1;
				for (int i = 0; i < cnt; i++)
					can_go[seq[i]] = i <= m;
				if (query(rt, u))
				{
					res = m;
					r = m - 1;
				}
				else
					l = m + 1;
			}
			add_edge(u, seq[res]);
			rem[seq[res]] = false;
		}
	}
}
void add(int u)
{
	vis[u] = 2;
	while (!direct(u))
		add(get_nxt(u));
	find_edge(u);
	vis[u] = 1;
}
void Detect(int T, int N)
{
	n = N;
	vis[0] = 1;
	for (int i = 1; i < n; i++)
	{
		if (!vis[i])
			add(i);
	}
}

Compilation message (stderr)

park.cpp: In function 'int get_nxt(int)':
park.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
park.cpp: In function 'void find_edge(int)':
park.cpp:91:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~

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