Submission #1282607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282607		nikaa123	Park (JOI17_park)	C++20	0 / 100	492 ms	327680 KiB

park

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

static int visited[1405];
vector <int> leaf;
int cnt[1405];
int p[1405];
vector <vector<int>> v(1405);
vector <int> nodes;

int N;

bool check(int node, int pref, vector <int> v) {
	if (node > N-1 || node <= 0) return false;
	int a[N]= {0};
	if (pref>0) {
		for (int i = 0; i <= pref; i++) {
			a[v[i]] = 1;
		}
	}
	for (int i = 0; i < N; i++) {
		if (visited[i]) a[i] = 1;
	}
	a[0] = 1;
	a[node] = 1;
	return Ask(0,node,a);
}

bool check1(int node, int pref, vector <int> v) {
	if (node > N-1 || node <= 0) return false;
	int a[N] = {0};
	for (int i = 0; i < N; i++) {
		if (visited[i]) a[i] = 1;
	}
	for (int i = 0; i <= v.size()-1; i++) {
		a[v[i]] = 0;
	}
	for (int i = 0; i <= pref; i++) {
		a[v[i]] = 1;
	}
	a[0] = 1;
	a[node] = 1;
	return Ask(0,node,a);
}

void Detect(int T, int n) {
	N = n;
	int root = 0;
	visited[root] = 0;
	stack <int> s;
	for (int i = 1; i < N; i++) {
		nodes.push_back(i);
	}
	for (int i = 0; i < N; i++) {
		if (visited[i]) continue;
		s.push(i);
		auto it = find(nodes.begin(),nodes.end(),i);
		nodes.erase(it);
		while (!s.empty()) {
			int node = s.top();
			if (check(node,-1,{})) {
				int l = 0;int  r = leaf.size()-1;
				int res;
				while (l <= r) {
					int mid = (l+r)/2;
					if (check1(node,mid,leaf)) {
						res = leaf[mid];
						r = mid - 1;
					} else {
						l = mid + 1;
					}
				}	
				cnt[res]++;
				if (cnt[res] > 1) {
					auto it = find(leaf.begin(),leaf.end(),res);
					leaf.erase(it);
				}
				p[node] = res;
				leaf.push_back(node);
				visited[node] = 1;
				s.pop();
			} else {
				int l = 0; int r = nodes.size()-1;
				int res = -1;
				while (l <= r) {
					int mid  = (l+r)/2;
					if (check(node,mid,nodes)) {
						res = nodes[mid];
						r = mid - 1;
					} else {
						l = mid + 1;
					}
				}
				s.push(res);
				auto it = find(nodes.begin(),nodes.end(),res);
				nodes.erase(it);
			}			
		}
	}

	for (int i = 1; i < N; i++) {
		// if (p[i] >= N) exit(0);
		if (p[i] <0 || p[i] >= N) continue;
		Answer(min(i,p[i]),max(i,p[i]));
	}
	


}

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