oj.uz

Submission #21024

# Submission time Handle Problem Language Result Execution time Memory
21024 2017-03-29T16:04:55 Z model_code Park (JOI17_park) C++11
100 / 100
 513 ms 1792 KB 
#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);
}

Compilation message

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1792 KB Output is correct
2 Correct 6 ms 1792 KB Output is correct
3 Correct 6 ms 1792 KB Output is correct
4 Correct 16 ms 1792 KB Output is correct
5 Correct 36 ms 1792 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 1792 KB Output is correct
2 Correct 153 ms 1792 KB Output is correct
3 Correct 203 ms 1792 KB Output is correct
4 Correct 469 ms 1792 KB Output is correct
5 Correct 493 ms 1792 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 1792 KB Output is correct
2 Correct 236 ms 1792 KB Output is correct
3 Correct 259 ms 1792 KB Output is correct
4 Correct 213 ms 1792 KB Output is correct
5 Correct 283 ms 1792 KB Output is correct
6 Correct 236 ms 1792 KB Output is correct
7 Correct 233 ms 1792 KB Output is correct
8 Correct 253 ms 1792 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1792 KB Output is correct
2 Correct 319 ms 1792 KB Output is correct
3 Correct 316 ms 1792 KB Output is correct
4 Correct 319 ms 1792 KB Output is correct
5 Correct 356 ms 1792 KB Output is correct
6 Correct 333 ms 1792 KB Output is correct
7 Correct 353 ms 1792 KB Output is correct
8 Correct 293 ms 1792 KB Output is correct
9 Correct 303 ms 1792 KB Output is correct
10 Correct 353 ms 1792 KB Output is correct
11 Correct 343 ms 1792 KB Output is correct
12 Correct 316 ms 1792 KB Output is correct
13 Correct 406 ms 1792 KB Output is correct
14 Correct 336 ms 1792 KB Output is correct
15 Correct 416 ms 1792 KB Output is correct
16 Correct 253 ms 1792 KB Output is correct
17 Correct 506 ms 1792 KB Output is correct
18 Correct 339 ms 1792 KB Output is correct
19 Correct 436 ms 1792 KB Output is correct
20 Correct 333 ms 1792 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 1792 KB Output is correct
2 Correct 376 ms 1792 KB Output is correct
3 Correct 313 ms 1792 KB Output is correct
4 Correct 356 ms 1792 KB Output is correct
5 Correct 386 ms 1792 KB Output is correct
6 Correct 426 ms 1792 KB Output is correct
7 Correct 386 ms 1792 KB Output is correct
8 Correct 383 ms 1792 KB Output is correct
9 Correct 366 ms 1792 KB Output is correct
10 Correct 309 ms 1792 KB Output is correct
11 Correct 329 ms 1792 KB Output is correct
12 Correct 356 ms 1792 KB Output is correct
13 Correct 323 ms 1792 KB Output is correct
14 Correct 386 ms 1792 KB Output is correct
15 Correct 353 ms 1792 KB Output is correct
16 Correct 253 ms 1792 KB Output is correct
17 Correct 513 ms 1792 KB Output is correct
18 Correct 333 ms 1792 KB Output is correct