oj.uz

답안 #29010

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29010 2017-07-18T06:01:06 Z 김현수(#1170) Park (JOI17_park) C++14
0 / 100
 479 ms 2316 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 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 S = 0, E = n;
	while(S<E) {
		int M = (S+E)/2;
		for(int i=0;i<n;i++) {
			pl[i] = (dn[i] || i<M);
		}
		pl[I] = true;
		Ask(0, I, pl) ? E = M : S = M+1;
	}
	if(S) add(S);
	for(int i=0;i<n;i++) tr[i].clear();
	fill(vis, vis+n, 0); gettree(0, -1);
	adde(0, I);
}

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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2192 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 356 ms 2316 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 436 ms 2276 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 329 ms 2280 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 479 ms 2284 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -