oj.uz

Submission #97012

# Submission time Handle Problem Language Result Execution time Memory
97012 2019-02-13T09:54:03 Z diamond_duke Park (JOI17_park) C++11
100 / 100
 376 ms 732 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 10 ms 384 KB Output is correct
3 Correct 11 ms 512 KB Output is correct
4 Correct 18 ms 384 KB Output is correct
5 Correct 39 ms 368 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 572 KB Output is correct
2 Correct 150 ms 512 KB Output is correct
3 Correct 208 ms 648 KB Output is correct
4 Correct 359 ms 584 KB Output is correct
5 Correct 334 ms 644 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 532 KB Output is correct
2 Correct 199 ms 540 KB Output is correct
3 Correct 219 ms 512 KB Output is correct
4 Correct 194 ms 504 KB Output is correct
5 Correct 244 ms 636 KB Output is correct
6 Correct 218 ms 512 KB Output is correct
7 Correct 202 ms 504 KB Output is correct
8 Correct 215 ms 632 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 384 KB Output is correct
2 Correct 254 ms 628 KB Output is correct
3 Correct 236 ms 496 KB Output is correct
4 Correct 277 ms 632 KB Output is correct
5 Correct 222 ms 504 KB Output is correct
6 Correct 238 ms 632 KB Output is correct
7 Correct 276 ms 632 KB Output is correct
8 Correct 232 ms 632 KB Output is correct
9 Correct 251 ms 512 KB Output is correct
10 Correct 255 ms 512 KB Output is correct
11 Correct 252 ms 512 KB Output is correct
12 Correct 311 ms 512 KB Output is correct
13 Correct 268 ms 632 KB Output is correct
14 Correct 244 ms 512 KB Output is correct
15 Correct 252 ms 732 KB Output is correct
16 Correct 230 ms 512 KB Output is correct
17 Correct 376 ms 640 KB Output is correct
18 Correct 244 ms 636 KB Output is correct
19 Correct 291 ms 512 KB Output is correct
20 Correct 232 ms 604 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 532 KB Output is correct
2 Correct 283 ms 632 KB Output is correct
3 Correct 254 ms 508 KB Output is correct
4 Correct 264 ms 636 KB Output is correct
5 Correct 282 ms 504 KB Output is correct
6 Correct 306 ms 532 KB Output is correct
7 Correct 278 ms 644 KB Output is correct
8 Correct 251 ms 644 KB Output is correct
9 Correct 254 ms 632 KB Output is correct
10 Correct 261 ms 604 KB Output is correct
11 Correct 283 ms 516 KB Output is correct
12 Correct 252 ms 632 KB Output is correct
13 Correct 224 ms 504 KB Output is correct
14 Correct 305 ms 636 KB Output is correct
15 Correct 229 ms 496 KB Output is correct
16 Correct 218 ms 632 KB Output is correct
17 Correct 341 ms 632 KB Output is correct
18 Correct 221 ms 632 KB Output is correct