oj.uz

Submission #568305

# Submission time Handle Problem Language Result Execution time Memory
568305 2022-05-25T07:59:13 Z blue Park (JOI17_park) C++17
67 / 100
 1016 ms 31288 KB 
#include "park.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define sz(x) int(x.size())

int N;
const int maxN = 1400;

static int Place[maxN];
vi parent(maxN, 0);

vi inserted(maxN, 0);

vi children[maxN];


bool ask(int A, int B, int Place[])
{
	return Ask(min(A, B), max(A, B), Place);
}

void answer(int a, int b)
{
	Answer(min(a, b), max(a, b));
}





bool connected(int u, int v)
{
	// cerr << "connected\n";
	for(int i = 0; i < N; i++)
		Place[i] = 0;

	Place[u] = Place[v] = 1;

	return ask(u, v, Place);
}

void dfs(int u, int x, int y, vi& res, vi& vis)
{
	vis[u] = 1;

	for(int v : children[u])
		dfs(v, x, y, res, vis);

	if(u != x && u != y)
		res.push_back(u);
}

vi ordering(int x, int y)
{
	vi vis(N, 0);
	vi res;
	dfs(0, x, y, res, vis);

	for(int i = 0; i < N; i++)
		if(!vis[i] && i != x && i != y)
			res.push_back(i);

	return res;
}

// int xyz = 0;


void insert_node(int u, int a)
{
	if(inserted[u]) return;

	// cerr << "insert node " << u << ' ' << a << '\n';
	// xyz++;
	// if(xyz>=10)
	// 	while(1);

	if(connected(u, a))
	{
		parent[u] = a;
		children[a].push_back(u);

		inserted[u] = 1;

		return;
	}

	vi searchlist = ordering(u, a);
	// cerr << u << ' ' << a << " : ";
	// for(int x : searchlist)
	// 	cerr << x << ' ';
	// cerr << '\n';

	while(sz(searchlist) > 1)
	{
		int md = sz(searchlist)/2;

		vi lft, rgt;
		for(int i = 0; i < sz(searchlist); i++)
		{
			if(i < md)
				lft.push_back(searchlist[i]);
			else
				rgt.push_back(searchlist[i]);
		}

		for(int i = 0; i < N; i++)
			Place[i] = 1;

		for(int f : lft)
			Place[f] = 0;

		if(!ask(u, a, Place))
			searchlist = lft;
		else
			searchlist = rgt;
	}

	// cerr << u << ' ' << a << " : " << "z = " << searchlist[0] << '\n';

	int z = searchlist[0];

	insert_node(u, z);
	insert_node(z, a);
}

void Detect(int T, int N_) 
{
	N = N_;
	inserted[0] = 1;
                     
	for(int i = 1; i < N; i++)
		insert_node(i, 0);

	for(int i = 1; i < N; i++)
		answer(i, parent[i]);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2772 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 796 KB Output is correct
2 Correct 137 ms 596 KB Output is correct
3 Correct 129 ms 2756 KB Output is correct
4 Correct 128 ms 840 KB Output is correct
5 Correct 142 ms 728 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 612 KB Output is correct
2 Correct 244 ms 500 KB Output is correct
3 Correct 255 ms 508 KB Output is correct
4 Correct 261 ms 500 KB Output is correct
5 Correct 258 ms 508 KB Output is correct
6 Correct 274 ms 512 KB Output is correct
7 Correct 240 ms 468 KB Output is correct
8 Correct 264 ms 492 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 468 KB Output is correct
2 Correct 243 ms 556 KB Output is correct
3 Correct 244 ms 532 KB Output is correct
4 Correct 259 ms 564 KB Output is correct
5 Correct 213 ms 648 KB Output is correct
6 Correct 168 ms 784 KB Output is correct
7 Correct 218 ms 712 KB Output is correct
8 Correct 229 ms 564 KB Output is correct
9 Correct 240 ms 552 KB Output is correct
10 Correct 244 ms 752 KB Output is correct
11 Correct 206 ms 668 KB Output is correct
12 Correct 228 ms 596 KB Output is correct
13 Correct 221 ms 624 KB Output is correct
14 Correct 212 ms 620 KB Output is correct
15 Correct 211 ms 624 KB Output is correct
16 Correct 272 ms 512 KB Output is correct
17 Correct 139 ms 748 KB Output is correct
18 Correct 224 ms 660 KB Output is correct
19 Correct 181 ms 676 KB Output is correct
20 Correct 264 ms 588 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1016 ms 31288 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -