제출 #1282588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282588		nikaa123	Park (JOI17_park)	C++20	0 / 100	2096 ms	49028 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);

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;
	leaf.push_back(0);
	for (int i = 0; i < N; i++) {
		if (visited[i]) continue;
		s.push(i);
		while (!s.empty()) {
			int node = s.top();
			if (!check(node,-1,{10,10})) {
				vector <int> nodes;
				for (int j = 0; j < N; j++) {
					if (!visited[j]) nodes.push_back(j);
				}
				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);
			} else {
				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]++;
				cnt[node]++;
				if (cnt[res] > 1) {
					auto it = find(leaf.begin(),leaf.end(),res);
					leaf.erase(it);
				}
				if (cnt[node] == 1) {
					leaf.push_back(node);
				}
				
				p[node] = res;
				visited[node] = 1;
				s.pop();
			}
		}
	}

	for (int i = 0; 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]));
		v[i].push_back(p[i]);
		v[p[i]].push_back(i);
	}
	


}

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