Submission #1234774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234774		emptypringlescan	Park (JOI17_park)	C++17	67 / 100	1363 ms	7324 KiB

park

#include "park.h"
#include <bits/stdc++.h>
using namespace std;
static int place[1400];
int n;
int adj[1405][1405],tree[1405];
vector<int> pre;
void dfs(int x, int p){
	pre.push_back(x);
	for(int i=0; i<n; i++){
		if(adj[x][i]&&i!=p) dfs(i,x);
	}
}
void Detect(int T, int N) {
	n=N;
	tree[0]=1;
	for(int i=1; i<n; i++){
		if(tree[i]) continue;
		pre.clear();
		dfs(0,-1);
		int tsz=0;
		for(int j=0; j<n; j++) tsz+=tree[j];
		assert(tsz==(int)pre.size());
		//for(int j:pre) cout << j << ' ';
		//cout << '\n';
		int lo=0,hi=(int)pre.size()-1,mid;
		while(lo<hi){
			mid=(lo+hi)/2;
			for(int j=0; j<=mid; j++) place[pre[j]]=1;
			for(int j=mid+1; j<(int)pre.size(); j++) place[pre[j]]=0;
			for(int j=0; j<n; j++) if(!tree[j]) place[j]=1;
			//cout << 0 << ' ' << i << '\n';
			//for(int j=0; j<n; j++) cout << place[j] << ' ';
			//cout << '\n';
			int x=Ask(0,i,place);
			//cout << x << '\n';
			if(x) hi=mid;
			else lo=mid+1;
		}
		//cout << lo << '\n';
		vector<pair<int,int> > seg={{pre[lo],i}};
		while(!seg.empty()){
			pair<int,int> yay=seg.back();
			if(yay.first>yay.second) swap(yay.first,yay.second);
			//assert(yay.first!=yay.second);
			seg.pop_back();
			lo=0,hi=n;
			while(lo<hi){
				mid=(lo+hi)/2;
				for(int j=0; j<n; j++) place[j]=0;
				for(int j=0; j<=mid; j++) if(!tree[j]) place[j]=1;
				place[yay.first]=1; place[yay.second]=1;
				if(Ask(yay.first,yay.second,place)) hi=mid;
				else lo=mid+1;
			}
			//if(lo==n){
				//cout << yay.first << ' ' << yay.second << '\n';
				//assert(false);
			//}
			if(lo==0){
				adj[yay.first][yay.second]=1;
				adj[yay.second][yay.first]=1;
				//cout << yay.first << ' ' << yay.second << '\n';
				tree[yay.first]=1; tree[yay.second]=1;
			}
			else{
				assert(!tree[lo]);
				seg.push_back({yay.first,lo});
				seg.push_back({lo,yay.second});
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(adj[i][j]) Answer(i,j);
		}
	}
}

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