oj.uz

답안 #29024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29024 2017-07-18T06:31:00 Z khsoo01 Park (JOI17_park) C++11
100 / 100
 526 ms 2324 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2192 KB Output is correct
2 Correct 6 ms 2192 KB Output is correct
3 Correct 6 ms 2192 KB Output is correct
4 Correct 19 ms 2192 KB Output is correct
5 Correct 23 ms 2192 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 499 ms 2324 KB Output is correct
2 Correct 186 ms 2324 KB Output is correct
3 Correct 249 ms 2324 KB Output is correct
4 Correct 499 ms 2324 KB Output is correct
5 Correct 509 ms 2324 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 2324 KB Output is correct
2 Correct 276 ms 2324 KB Output is correct
3 Correct 293 ms 2324 KB Output is correct
4 Correct 253 ms 2324 KB Output is correct
5 Correct 323 ms 2324 KB Output is correct
6 Correct 269 ms 2324 KB Output is correct
7 Correct 273 ms 2324 KB Output is correct
8 Correct 313 ms 2324 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 2324 KB Output is correct
2 Correct 333 ms 2324 KB Output is correct
3 Correct 333 ms 2324 KB Output is correct
4 Correct 343 ms 2324 KB Output is correct
5 Correct 396 ms 2324 KB Output is correct
6 Correct 353 ms 2324 KB Output is correct
7 Correct 399 ms 2324 KB Output is correct
8 Correct 323 ms 2324 KB Output is correct
9 Correct 329 ms 2324 KB Output is correct
10 Correct 389 ms 2324 KB Output is correct
11 Correct 376 ms 2324 KB Output is correct
12 Correct 333 ms 2324 KB Output is correct
13 Correct 389 ms 2324 KB Output is correct
14 Correct 339 ms 2324 KB Output is correct
15 Correct 406 ms 2324 KB Output is correct
16 Correct 323 ms 2324 KB Output is correct
17 Correct 509 ms 2324 KB Output is correct
18 Correct 339 ms 2324 KB Output is correct
19 Correct 443 ms 2324 KB Output is correct
20 Correct 353 ms 2324 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 2324 KB Output is correct
2 Correct 386 ms 2324 KB Output is correct
3 Correct 333 ms 2324 KB Output is correct
4 Correct 349 ms 2324 KB Output is correct
5 Correct 399 ms 2324 KB Output is correct
6 Correct 426 ms 2324 KB Output is correct
7 Correct 416 ms 2324 KB Output is correct
8 Correct 423 ms 2324 KB Output is correct
9 Correct 379 ms 2324 KB Output is correct
10 Correct 329 ms 2324 KB Output is correct
11 Correct 339 ms 2324 KB Output is correct
12 Correct 396 ms 2324 KB Output is correct
13 Correct 333 ms 2324 KB Output is correct
14 Correct 403 ms 2324 KB Output is correct
15 Correct 373 ms 2324 KB Output is correct
16 Correct 346 ms 2324 KB Output is correct
17 Correct 526 ms 2324 KB Output is correct
18 Correct 336 ms 2324 KB Output is correct