Submission #1234735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234735		emptypringlescan	Park (JOI17_park)	C++17	0 / 100	48 ms	6976 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 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<i; 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);
			if(x) hi=mid;
			else lo=mid+1;
		}
		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-1;
			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==0){
				adj[yay.first][yay.second]=1;
				adj[yay.second][yay.first]=1;
				tree[yay.first]=1; tree[yay.second]=1;
			}
			else{
				assert(!tree[lo]);
				seg.push_back({yay.first,lo});
				seg.push_back({lo,yay.second});
				assert(yay.first!=lo&&yay.second!=lo);
			}
		}
	}
	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: 0 / 10
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30
• Subtask 5: 0 / 23