Submission #521764

#	Time	Username	Problem	Language	Result	Execution time	Memory
521764		ainta	Park (JOI17_park)	C++17	100 / 100	554 ms	616 KiB

park

#include "park.h"
#include <cstdio>
#include <vector>
using namespace std;
#define si(x) (int)(x.size())

static int Place[1400], n, fin[1400], chk[1400], U[1400], vi[1400];
static vector<int>E[1400], TP, PP;
void Tra(int a){
	vi[a]=1;
	TP.push_back(a);
	for(auto &t: E[a]){
		if(U[t] || vi[t])continue;
		Tra(t);
	}
}
void Go(int rt, int a, int cer){
	for(int i=0;i<n;i++)vi[i]=0;
	TP.clear();
	Tra(rt);
	int m = si(TP);
	if(!cer){
		for(int i=0;i<n;i++)Place[i]=0;
		for(int i=0;i<m;i++)Place[TP[i]]=1;
		Place[a] = 1;
		if(!Ask(min(rt,a),max(rt,a),Place))return;
	}
	int b = 1, e = m-1, r = m;
	while(b<=e){
		int mid = (b+e)>>1;
		for(int i=0;i<n;i++)Place[i]=0;
		for(int i=0;i<mid;i++)Place[TP[i]]=1;
		Place[a]=1;
		if(Ask(min(rt,a),max(rt,a),Place)){
			r = mid;
			e = mid-1;
		}
		else b = mid+1;
	}
	int x = TP[r-1];
	PP.push_back(x);
	U[x] = 1;
	for(auto &y : E[x]){
		if(!U[y]){
			Go(y, a, 0);
		}
	}
}
void Add(int a){
	int i;
	PP.clear();
	for(i=0;i<n;i++)U[i]=0;
	Go(0, a, 1);
	fin[a] = 1;
	for(auto &t: PP){
		Answer(min(a, t),max(a,t));
		E[a].push_back(t);
		E[t].push_back(a);
	}
}
void DFS(int a){
	chk[a] = 1;
	int c = 0;
	for(int i=0;i<n;i++){
		if(chk[i]||fin[i])continue;
		c++;
	}
	int b = 0, e = c, mid, r = -1;
	while(b<=e){
		mid = (b+e)>>1;
		for(int i=0;i<n;i++){
			Place[i] = fin[i];
		}
		int t=0;
		for(int i=0;i<n;i++){
			if(chk[i]||fin[i])continue;
			if(t<mid){
				Place[i] = 1;
			}
			t++;
		}
		Place[a] = 1;
		if(Ask(0, a, Place)){
			r = mid;
			e = mid-1;
		}
		else b = mid+1;
	}
	if(r == 0){
		Add(a);
		return;
	}
	else{
		int t=0, x = -1;
		for(int i=0;i<n;i++){
			if(chk[i]||fin[i])continue;
			t++;
			if(t==r)x = i;
		}
		DFS(x);
		DFS(a);
	}
}
void Detect(int T, int N) {
	n = N;
	int i;
	fin[0]=1;
	for(i=1;i<N;i++){
		if(fin[i])continue;
		DFS(i);
	}
}

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