Submission #125325

#	Time	Username	Problem	Language	Result	Execution time	Memory
125325		khsoo01	Park (JOI17_park)	C++11	100 / 100	314 ms	804 KiB

park

#include<bits/stdc++.h>
#include "park.h"
using namespace std;

namespace {
	const int N = 1505;
	int place[N];
	bool vis[N], blk[N];

	int n;
	vector<int> tree[N];
}

int check (int S, int E, vector<int> &O) {
	for(int i=0;i<n;i++) place[i] = 0;
	for(auto &T : O) place[T] = 1;
	place[S] = 1;
	place[E] = 1;
	return Ask(min(S, E), max(S, E), place);
}

int Find (int A, int B, vector<int> &O) {
	int S = 0, E = O.size();
	while(S<E) {
		int M = (S+E)/2;
		vector<int> V;
		for(int i=0;i<M;i++) {
			V.push_back(O[i]);
		}
		check(A, B, V) ? E = M : S = M+1;
	}
	return (S ? O[S-1] : A);
}

void preorder (int C, int P, vector<int> &O) {
	O.push_back(C);
	for(auto &T: tree[C]) {
		if(T == P || blk[T]) continue;
		preorder(T, C, O);
	}
}

void construct (int S, int E, vector<int> &O) {
	vis[E] = true;
	int M = Find(S, E, O);
	if(M == S) {
		tree[S].push_back(E);
		tree[E].push_back(S);
		Answer(min(S, E), max(S, E));
	}
	else {
		construct(S, M, O);
		construct(M, E, O);
	}
}

void Try (int P, int I) {
	vector<int> V;
	preorder(I, -1, V);
	if(!check(I, P, V)) return;
	int J = Find(I, P, V);
	Answer(min(P, J), max(P, J));
	blk[J] = true;
	for(auto &T : tree[J]) {
		if(!blk[T]) Try(P, T);
	}
}

void Detect (int T, int N) {
	n = N;
	for(int i=1;i<n;i++) {
		if(vis[i]) continue;
		vector<int> V;
		for(int j=1;j<n;j++) {
			if(tree[j].empty()) V.push_back(j);
		}
		preorder(0, -1, V);
		int M = Find(0, i, V);
		if(tree[M].empty()) M = 0;
		V.clear();
		for(int j=1;j<n;j++) {
			if(tree[j].empty()) V.push_back(j);
		}
		construct(M, i, V);
	}
	vector<int> X;
	preorder(0, -1, X);
	for(int i=(int)X.size()-1;i>0;i--) {
		for(int j=0;j<X.size();j++) {
			blk[X[j]] = (j >= i);
		}
		int I;
		for(auto &T : tree[X[i]]) {
			if(!blk[T]) {I = T; break;}
		}
		blk[I] = true;
		for(auto &T : tree[I]) {
			if(!blk[T]) Try(X[i], T);
		}
	}
}

Compilation message (stderr)

park.cpp: In function 'void Detect(int, int)':
park.cpp:89:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<X.size();j++) {
               ~^~~~~~~~~
park.cpp:92:7: warning: 'I' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int I;
       ^

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