Submission #1282669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282669		nikaa123	Park (JOI17_park)	C++20	0 / 100	257 ms	892 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
// #define int int

int p[1405];
int f[1405];
int n;

vector <int> lst, nodes,vis(1405);
vector <vector<int>> v(1405);

void colect(int x) {
	nodes.push_back(x);
	for (auto to:v[x]) {
		if (!vis[to]) colect(to);
	}
}

void dfs(int x, int node) {
	while (true) {
		if (vis[x]) return;
		nodes.clear();
		colect(x);
		for (int i = 0; i < n; i++) {
			p[i] = 0;
		}
		for (auto to:nodes) {
			p[to] = 1;
		}
		p[node] = 1;
		if (!Ask(min(node,x),max(node,x),p)) {
			return;
		}
		int l = 0; int r =(nodes.size())-1;
		int res = -1;
		while (l <= r) {
			int mid = (l+r)/2;
			for (int i = 0; i < n; i++) {
				p[i] = 0;
			}
			for (int i = 0; i <= mid; i++) {
				p[nodes[i]] = 1;
			}
			p[node] = p[x] = 1;
			if (Ask(min(node,x),max(node,x),p)) {
				res = nodes[mid];
				r = mid - 1;
			} else {
				l = mid +1;
			}
		}
		vis[res] = 1;
		lst.push_back(res);
		for (auto to:v[res]) {
			dfs(to,node);
		}
	}
}

void explore(int x) {
	if (f[x]) {
		return;
	}

	for (int i = 0; i < n; i++) {
		vis[i] = 0;
		p[i] = f[i];
	}
	p[x] = 1;
	while (!Ask(0,x,p)) {
		int l = 0; int r = n-1;
		int res;
		while (l <= r) {
			int mid = (l+r)/2;
			for (int i = 0; i < n; i++) {
				if (f[i] || i<= mid) {
					p[i] = 1;
				}
			}
			if (Ask(0,x,p)) {
				res = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		explore(res);
	}
	lst.clear();
	dfs(0,x);

	for (auto u:lst) {
		Answer(min(u,x),max(u,x));
		p[x] = u;
		v[u].push_back(x);
	}
	f[x] = 1;
}


void Detect(int T, int N) {
	n = N;
	for (int i = 0; i < n; i++) {
		f[i] = 0;
		p[i] = 0;
	}
	f[0] = 1;
	for (int i = 0; i < n; i++) {
		if (f[i]) continue;
		explore(i);
	}
}

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