Submission #97012

#	Time	Username	Problem	Language	Result	Execution time	Memory
97012		diamond_duke	Park (JOI17_park)	C++11	100 / 100	376 ms	732 KiB

park

#include "park.h"
#include <algorithm>
#include <cstring>
int lst[2005], to[3005], pre[3005], vis[2005], seq[2005], tot, n, cnt;
bool can_go[2005], rem[2005], in[2005];
inline bool query(int u, int v)
{
	if (u > v)
		std::swap(u, v);
	static int qry[2005];
	for (int i = 0; i < n; i++)
		qry[i] = can_go[i];
	return Ask(u, v, qry);
}
inline void add_edge(int u, int v)
{
	if (u > v)
		std::swap(u, v);
	Answer(u, v);
	auto add_e = [&] (int x, int y)
	{
		to[tot] = y;
		pre[tot] = lst[x];
		lst[x] = tot++;
	};
	add_e(u, v);
	add_e(v, u);
}
inline int get_min(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 i = lst[u]; ~i; i = pre[i])
	{
		if (rem[to[i]])
			clear(to[i]);
	}
}
void dfs(int u)
{
	seq[cnt++] = u;
	in[u] = true;
	for (int i = lst[u]; ~i; i = pre[i])
	{
		if (rem[to[i]] && !in[to[i]])
			dfs(to[i]);
	}
}
inline void get_edge(int u)
{
	for (int i = 0; i < n; i++)
		rem[i] = vis[i] == 1;
	int rt = 0;
	while (rt < n)
	{
		if (!rem[rt])
		{
			rt++;
			continue;
		}
		memcpy(can_go, rem, n);
		can_go[u] = true;
		if (!query(u, rt))
		{
			clear(rt++);
			continue;
		}
		cnt = 0;
		memset(in, false, n);
		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;
	}
}
inline bool connect(int u)
{
	for (int i = 0; i < n; i++)
		can_go[i] = vis[i] == 1;
	can_go[u] = true;
	return query(0, u);
}
void add_node(int u)
{
	vis[u] = 2;
	while (!connect(u))
		add_node(get_min(u));
	get_edge(u);
	vis[u] = 1;
}
void Detect(int, int N)
{
	n = N;
	memset(lst, -1, n << 2);
	vis[0] = 1;
	for (int i = 0; i < n; i++)
	{
		if (!vis[i])
			add_node(i);
	}
}

Compilation message (stderr)

park.cpp: In function 'int get_min(int)':
park.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
park.cpp: In function 'void get_edge(int)':
park.cpp:94:14: 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