Submission #29024

#	Time	Username	Problem	Language	Result	Execution time	Memory
29024		khsoo01	Park (JOI17_park)	C++11	100 / 100	526 ms	2324 KiB

park

#include<bits/stdc++.h>
#include "park.h"
using namespace std;
const int N = 1505;

static int n, pl[N];
static bool dn[N], vis[N], blk[N];

static vector<int> adj[N], tr[N], ord;

void newedg (int A, int B) {
	if(A > B) swap(A, B);
	Answer(A, B);
	adj[A].push_back(B);
	adj[B].push_back(A);
}

void gettree (int I, int P) {
	if(vis[I]) return;
	vis[I] = true;
	if(~P) {
		tr[I].push_back(P);
		tr[P].push_back(I);
	}
	for(auto &T : adj[I]) gettree(T, I);
}

void ins (int I, int P) {
	if(blk[I]) return;
	ord.push_back(I);
	for(auto &T : tr[I]) {
		if(T != P) ins(T, I);
	}
}

void ins (int I) {
	if(vis[I]) return;
	vis[I] = true;
	ord.push_back(I);
	for(auto &T : adj[I]) ins(T);
}

void adde (int R, int I) {
	ord.clear(); ins(R, -1);
	int S = 1, E = ord.size();
	while(S<E) {
		int M = (S+E)/2;
		fill(pl, pl+n, 0);
		for(int i=0;i<M;i++) pl[ord[i]] = true;
		pl[I] = true;
		Ask(min(R, I), max(R, I), pl) ? E = M : S = M+1;
	}
	R = ord[S-1]; blk[R] = true;
	newedg(I, R);
	for(auto &T : tr[R]) {
		if(blk[T]) continue;
		ord.clear(); ins(T, -1);
		fill(pl, pl+n, 0);
		for(auto &P : ord) pl[P] = true;
		pl[I] = true;
		if(Ask(min(T, I), max(T, I), pl)) adde(T, I);
	}
	blk[R] = false;
}

void add (int I) {
	dn[I] = true;
	int R;
	while(true) {
		fill(vis, vis+n, 0);
		ord.clear(); ins(0);
		for(int i=0;i<n;i++) {
			if(!vis[i]) ord.push_back(i);
		}
		int S = 1, E = n;
		while(S<E) {
			int M = (S+E)/2;
			for(int i=0;i<M;i++) pl[ord[i]] = true;
			for(int i=M;i<n;i++) pl[ord[i]] = false;
			pl[I] = true;
			Ask(0, I, pl) ? E = M : S = M+1;
		}
		R = ord[S-1];
		if(!dn[R]) add(R);
		else break;
	}
	for(int i=0;i<n;i++) tr[i].clear();
	fill(vis, vis+n, 0);
	gettree(0, -1);
	blk[R] = true; newedg(R, I);
	for(auto &T : tr[R]) {
		if(blk[T]) continue;
		ord.clear(); ins(T, -1);
		fill(pl, pl+n, 0);
		for(auto &P : ord) pl[P] = true;
		pl[I] = true;
		if(Ask(min(T, I), max(T, I), pl)) adde(T, I);
	}
	blk[R] = false;
}

void Detect(int T, int N) {
	n = N; dn[0] = true;
	for(int i=1;i<n;i++) {
		if(!dn[i]) add(i);
	}
}

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