Submission #21024

#	Time	Username	Problem	Language	Result	Execution time	Memory
21024		model_code	Park (JOI17_park)	C++11	100 / 100	513 ms	1792 KiB

park

#include <stdio.h>
#include "park.h"

static int Place[9999];
static int checked[9999]; //0:not 1:checked 2:in_stack
static int edges[9999][9];
static int degree[9999];
static int N;
static int myAsk(int A,int B) {
	if(A>B) return myAsk(B,A);
	return Ask(A,B,Place);
}
static void myAnswer(int A,int B) {
	if(A>B) {
		Answer(B,A);
	} else {
		Answer(A,B);
	}
	edges[A][degree[A]++]=B;
	edges[B][degree[B]++]=A;
}
static int direct_connection(int now) {
	int i;
	for(i=0;i<N;i++) {
		Place[i]=0;
		if(checked[i]==1) Place[i]=1;
	}
	Place[now]=1;
	return myAsk(0,now);
}
static int find_new_node(int now) {
	int i;
	int minv=0; int maxv=N-1;
	while(minv<maxv) {
		int hf=(minv+maxv)/2;
		for(i=0;i<N;i++) Place[i]=0;
		for(i=0;i<=hf;i++) if(checked[i]!=2) Place[i]=1;
		for(i=hf+1;i<N;i++) if(checked[i]==1) Place[i]=1;
		Place[now]=1;
		if(myAsk(0,now)) {
			maxv=hf;
		} else {
			minv=hf+1;
		}
	}
	return minv;
}
static int rem[9999];
static int dfs_order_size;
static int dfs_order[9999];
static int dfs_order_checked[9999];
static void dfs_order_calc(int now) {
	dfs_order_checked[now]=1;
	dfs_order[dfs_order_size++]=now;
	int i;
	for(i=0;i<degree[now];i++) if(rem[edges[now][i]]==1&&dfs_order_checked[edges[now][i]]==0) dfs_order_calc(edges[now][i]);
}
static void dfs_delete(int now) {
	rem[now]=0;
	Place[now]=0;
	int i;
	for(i=0;i<degree[now];i++) if(rem[edges[now][i]]==1) dfs_delete(edges[now][i]);
}
static void find_edges(int now) {
	int cur,i;
	for(i=0;i<N;i++) rem[i]=0;
	for(i=0;i<N;i++) if(checked[i]==1) rem[i]=1;
	for(cur=0;cur<N;cur++) {
		while(rem[cur]) {
			for(i=0;i<N;i++) Place[i]=rem[i];
			Place[now]=1;
			if(myAsk(cur,now)) {
				dfs_order_size=0;
				for(i=0;i<N;i++) dfs_order_checked[i]=0;
				dfs_order_calc(cur);
				int minv=0; int maxv=dfs_order_size-1;
				while(minv<maxv) {
					int hf=(minv+maxv)/2;
					for(i=0;i<=hf;i++) Place[dfs_order[i]]=1;
					for(i=hf+1;i<dfs_order_size;i++) Place[dfs_order[i]]=0;
					if(myAsk(cur,now)==0) {
						minv=hf+1;
					} else {
						maxv=hf;
					}
				}
				myAnswer(now,dfs_order[minv]);
				rem[dfs_order[minv]]=0;
				Place[dfs_order[minv]]=0;
			} else {
				dfs_delete(cur);
			}
		}
	}
}
static void execute(int now) {
	checked[now]=2;
	while(direct_connection(now)==0) {
		int next=find_new_node(now);
		execute(next);
	}
	find_edges(now);
	checked[now]=1;
}
void Detect(int T,int N_get) {
	N=N_get;
	int i;
	checked[0]=1;
	for(i=1;i<N;i++) if(checked[i]==0) execute(i);
}

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