oj.uz

Submission #86907

# Submission time Handle Problem Language Result Execution time Memory
86907 2018-11-28T10:35:06 Z radoslav11 Park (JOI17_park) C++14
100 / 100
 469 ms 2024 KB 
/*
	https://codeforces.com/blog/entry/51010
*/

#include <bits/stdc++.h>
#include "park.h"
//#include "Lgrader.cpp"

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1400);

int n, state[MAXN];
static int Place[MAXN];
vector<int> adj[MAXN];

int query(int from, int to)
{
	if(from > to) swap(from, to);
	return Ask(from, to, Place);
}

void add_edge(int u, int v)
{
	adj[u].pb(v);
	adj[v].pb(u);

	if(u < v) Answer(u, v);
	else Answer(v, u);
}

int d[MAXN], rem[MAXN];
vector<int> bfs_order;

void gen_bfs_order(int src)
{
	bfs_order.clear();
	for(int i = 0; i < n; i++) d[i] = -1;

	queue<int> q;
	d[src] = 0;
	q.push(src);

	while(!q.empty())
	{
		int u = q.front();
		bfs_order.pb(u);
		q.pop();

		for(int v: adj[u])
			if(!rem[v] && d[v] == -1)
			{
				d[v] = d[u] + 1;
				q.push(v);
			}
	}
}

bool add_one_direct(int up, int u)
{
	gen_bfs_order(up);
	for(int i = 0; i < n; i++) Place[i] = 0;
	for(int v: bfs_order) Place[v] = 1;
	Place[u] = 1;

	if(!query(up, u)) return 0;

	int low = 0, high = SZ(bfs_order) - 1, ret, mid;
	while(low <= high)
	{
		mid = (low + high) >> 1;
		for(int i = 0; i < n; i++) Place[i] = 0;
		for(int i = 0; i <= mid; i++) Place[bfs_order[i]] = 1;
		Place[u] = 1;

		if(query(up, u))
			ret = mid, high = mid - 1;
		else 
			low = mid + 1;
	}

	add_edge(u, bfs_order[ret]);
	rem[bfs_order[ret]] = 1;
	return 1;
}

void dfs_clear(int u)
{
	rem[u] = 1;
	for(int v: adj[u])
		if(!rem[v])
			dfs_clear(v);
}

bool add_direct(int u)
{
	bool ret = 0;
	for(int i = 0; i < n; i++) rem[i] = 0;

	for(int up = 0; up < n; up++)
		while(!rem[up] && state[up] == 1)
		{
			if(add_one_direct(up, u)) ret = 1;
			else dfs_clear(up);			
		}

	return ret;
}

int get_new(int u)
{
	int low = 0, high = n - 1, mid, ret;
	while(low <= high)
	{
		mid = (low + high) >> 1;
		
		for(int i = 0; i < n; i++) Place[i] = (state[i] == 1);
		for(int i = 0; i <= mid; i++) if(state[i] != 2) Place[i] = 1;
		Place[u] = 1; 

		if(query(0, u))
			ret = mid, high = mid - 1;
		else
			low = mid + 1;
	}

	return ret;
}

void fix(int u)
{
	state[u] = 2;

	while(!add_direct(u))
	{
		int nw = get_new(u);
		fix(nw);
	}

	state[u] = 1;	
}

void Detect(int T, int N) 
{
	T = 0;
	n = N;

	for(int i = 0; i < n; i++) state[i] = 0;

	state[0] = 1;
	for(int i = 1; i < n; i++)
		if(!state[i])
			fix(i);
}

Compilation message

park.cpp: In function 'int get_new(int)':
park.cpp:134:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ret;
         ^~~
park.cpp: In function 'bool add_one_direct(int, int)':
park.cpp:89:27: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  add_edge(u, bfs_order[ret]);
                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 10 ms 624 KB Output is correct
3 Correct 13 ms 624 KB Output is correct
4 Correct 21 ms 732 KB Output is correct
5 Correct 44 ms 772 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 1088 KB Output is correct
2 Correct 168 ms 1088 KB Output is correct
3 Correct 248 ms 1088 KB Output is correct
4 Correct 459 ms 1164 KB Output is correct
5 Correct 434 ms 1204 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 1204 KB Output is correct
2 Correct 286 ms 1208 KB Output is correct
3 Correct 304 ms 1208 KB Output is correct
4 Correct 234 ms 1208 KB Output is correct
5 Correct 343 ms 1268 KB Output is correct
6 Correct 301 ms 1288 KB Output is correct
7 Correct 283 ms 1288 KB Output is correct
8 Correct 297 ms 1288 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 1296 KB Output is correct
2 Correct 309 ms 1300 KB Output is correct
3 Correct 313 ms 1372 KB Output is correct
4 Correct 319 ms 1380 KB Output is correct
5 Correct 302 ms 1384 KB Output is correct
6 Correct 321 ms 1424 KB Output is correct
7 Correct 319 ms 1424 KB Output is correct
8 Correct 282 ms 1424 KB Output is correct
9 Correct 288 ms 1492 KB Output is correct
10 Correct 322 ms 1520 KB Output is correct
11 Correct 302 ms 1520 KB Output is correct
12 Correct 285 ms 1520 KB Output is correct
13 Correct 319 ms 1520 KB Output is correct
14 Correct 295 ms 1616 KB Output is correct
15 Correct 317 ms 1616 KB Output is correct
16 Correct 298 ms 1620 KB Output is correct
17 Correct 446 ms 1620 KB Output is correct
18 Correct 301 ms 1684 KB Output is correct
19 Correct 345 ms 1812 KB Output is correct
20 Correct 287 ms 1812 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 1812 KB Output is correct
2 Correct 359 ms 1812 KB Output is correct
3 Correct 356 ms 1812 KB Output is correct
4 Correct 320 ms 1812 KB Output is correct
5 Correct 380 ms 1812 KB Output is correct
6 Correct 439 ms 1812 KB Output is correct
7 Correct 354 ms 1812 KB Output is correct
8 Correct 317 ms 1868 KB Output is correct
9 Correct 332 ms 1868 KB Output is correct
10 Correct 296 ms 1880 KB Output is correct
11 Correct 322 ms 1880 KB Output is correct
12 Correct 337 ms 1880 KB Output is correct
13 Correct 279 ms 1888 KB Output is correct
14 Correct 421 ms 1912 KB Output is correct
15 Correct 323 ms 1992 KB Output is correct
16 Correct 298 ms 1992 KB Output is correct
17 Correct 435 ms 2024 KB Output is correct
18 Correct 293 ms 2024 KB Output is correct