Submission #1234773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234773		salmon	Park (JOI17_park)	C++20	77 / 100	168 ms	17752 KiB

park

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

static int Place[1400];

namespace{

	int parent[1500];
	int d[1500];
	vector<int> nose[1500];
	int N;
	int md = 0;
	
	void connect(int A, int B){
		parent[B] = A;
		d[B] = d[A] + 1;
		md = max(md,d[B]);
		nose[d[B]].push_back(B);
	}

	void solve(int A, int B, vector<int> fill){
		//printf("%d %d\n",A,B);
		fill.push_back(B);
		
		for(int i = 0; i < N; i++) Place[i] = 0;
		for(int i : fill) Place[i] = 1;
		
		if(Ask(0,B,Place)){
			connect(A,B);
			return;
		}
		
		Place[B] = 1;
		
		vector<int> temp;
		
		for(int i = 1; i < N; i++){
			if(parent[i] == -1 && i != B){
				temp.push_back(i);
			}
		} 
		
		vector<int> temp1;
		
		while(true){
			for(int i = 0; i < N; i++) Place[i] = 0;
			for(int i : fill) Place[i] = 1;
			for(int i : temp) Place[i] = 1;
			
			temp1.clear();
			
			for(int i = temp.size()/2; i < temp.size(); i++){
				temp1.push_back(temp[i]);
				Place[temp[i]] = 0;
			} 
			
			if(!Ask(0,B,Place)){
				break;
			}
			else{
				for(int i : temp1) temp.pop_back();
			}
		}
		
		while(temp1.size() != 1){
			for(int i = 0; i < N; i++) Place[i] = 0;
			for(int i : fill) Place[i] = 1;
			for(int i : temp) Place[i] = 1;
			
			vector<int> temp2;
			
			for(int i = temp1.size()/2; i < temp1.size(); i++){
				temp2.push_back(temp1[i]);
				Place[temp1[i]] = 0;
			}
			
			if(Ask(0,B,Place)){
				for(int _ : temp2) temp1.pop_back();
			}
			else{
				temp1 = temp2;
			}
		}
		
		fill.pop_back();
		solve(A,temp1[0],fill);
		
		fill.clear();
		
		fill = {temp1[0]};
		while(fill.back() != 0) fill.push_back(parent[fill.back()]);
		
		solve(temp1[0],B,fill);
	}
}

void Detect(int T, int _N) {
	if(T == 1){
		N = _N;
		
		for(int i = 0; i < N; i++){
			for(int j = i + 1; j < N; j++){
				
				for(int k = 0; k < N; k++) Place[k] = 0;				
				
				Place[i] = 1;
				Place[j] = 1;
				
				if(Ask(i,j,Place)) Answer(i,j);
			}
		}
			
		return;
	}
	if(T == 5) return;
	
	N = _N;
	
	for(int i = 0 ; i < N; i++) Place[i] = 0;
	for(int i = 0; i < N; i++) parent[i] = -1;
	for(int i = 0; i < N; i++) d[i] = -1;
	
	for(int i = 0; i <= N; i++) nose[i].clear();
	
	nose[0] = {0};
	parent[0] = -5;
	d[0] = 0;
	
	while(true){
		for(int i = 0; i < N; i++){
			Place[i] = 1;
		}
		
		int in = -1;
		
		for(int i = 1; i < N; i++){
			if(parent[i] == -1){
				in = i;
			}
		}
		if(in == -1) break;
		
		//printf("in : %d %d\n",in,md);
		
		int s = 0;
		int e = md;
		while(s != e){
			int acc = 0;
			for(int i = s; i <= e; i++){
				acc += nose[i].size();
			}
			
			int acc1 = nose[s].size();
			int m = s;
			
			while(acc1 * 2 < acc){
				m++;
				acc1 += nose[m].size();
			}
			if(m != s) m--;
			
			//printf("%d %d %d\n",s,e,m);
			
			for(int i = 0; i < N; i++) Place[i] = 1;
			for(int i = 0; i < N; i++) if(d[i] > m) Place[i] = 0;
			
			if(Ask(0,in,Place)){
				e = m;
			}
			else{
				s = m + 1;
			}
		}
		
		//printf("OK %d\n",s);
		
		vector<int> temp = nose[s];
		
		while(temp.size() != 1){
			for(int i = 0; i < N; i++) Place[i] = 1;
			for(int i = 0; i < N; i++) if(d[i] >= s) Place[i] = 0;
			
			vector<int> temp1;
			
			for(int i = temp.size()/2; i < temp.size(); i++){
				Place[temp[i]] = 1;
				temp1.push_back(temp[i]);
			}
			
			if(Ask(0,in,Place)){
				temp = temp1;
			}
			else{
				for(int _ : temp1) temp.pop_back();
			}
		}
		//printf("OK %d\n",d[0]);
		int c = temp[0];
		
		for(int i = 0; i < N; i++) Place[i] = 0;
		for(int i = 0; i < N; i++) if(d[i] != -1 && d[i] <= s) Place[i] = 1;	
		Place[in] = 1;
		
		if(Ask(0,in,Place)){
			connect(c,in);
		}
		else{
			vector<int> tomp = {c};
			
			while(tomp.back() != 0){
				tomp.push_back(parent[tomp.back()]);
			}
			
			solve(c,in,tomp);
		}
	}
	
	for(int i = 1; i < N; i++) Answer(min(i,parent[i]),max(i,parent[i]));
}

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