Submission #412734

#	Time	Username	Problem	Language	Result	Execution time	Memory
412734		amoo_safar	Park (JOI17_park)	C++17	100 / 100	688 ms	972 KiB

park

#include "park.h"
#include<bits/stdc++.h>
#define pb push_back

using namespace std;

static int Place[1400];

const int N = 1405;

int Query(int u, int v){
	if(u > v) swap(u, v);
	return Ask(u, v, Place);
}
int n;
int added[N];
vector<int> ord, rem;

void Add(int u){
	if(added[u])
		return;

	rem = {u};
	for(int i = 0; i < n; i++)
		if(!added[i] && i != u)
			rem.pb(i);
	int L = 0, R = rem.size();
	while(L + 1 < R){
		int mid = (L + R) >> 1;
		
		memset(Place, 0, sizeof Place);
		for(auto x : ord)
			Place[x] = 1;
		
		for(int i = 0; i < mid; i++)
			Place[rem[i]] = 1;
		
		if(Query(ord[0], rem[0])) R = mid;
		else L = mid;
	}
	if(R == 1){
		added[u] = 1;
		ord.pb(u);
		return ;
	}
	int v = rem[L];
	Add(v);
	Add(u);
}

vector<int> G[N];
void Add_Edge(int u, int v){
	if(u > v) swap(u, v);
	Answer(u, v);
	// cerr << "!! " << u << ' ' << v << '\n';
	G[u].pb(v);
	G[v].pb(u);
}

vector<int> dfs;
int mk[N];
void DFS(int u){
	mk[u] = 1;
	dfs.pb(u);
	for(auto adj : G[u])
		if(!mk[adj])
			DFS(adj);
}
void Find_Edges(vector<int> V, int u){
	if(V.empty())
		return ;
	memset(Place, 0, sizeof Place);
	for(auto x : V)
		Place[x] = 1;
	Place[u] = 1;
	if(!Query(V[0], u)) return ;
	memset(mk, 1, sizeof mk);
	for(auto x : V)
		mk[x] = 0;
	dfs.clear();
	DFS(V[0]);
	
	assert(dfs.size() == V.size());

	int L = 0, R = V.size();
	while(L + 1 < R){
		int mid = (L + R) >> 1;
		for(int i = 0; i < (int) V.size(); i++)
			Place[dfs[i]] = (i < mid);
		if(Query(dfs[0], u))
			R = mid;
		else
			L = mid;
	}
	Add_Edge(u, dfs[L]);

	for(auto x : V)
		mk[x] = 0;
	mk[dfs[L]] = 1;
	vector< vector<int> > com;
	for(auto x : V){
		if(mk[x]) continue;
		dfs.clear();
		DFS(x);
		com.pb(dfs);
	}
	for(auto cm : com)
		Find_Edges(cm, u);
}

void Detect(int T, int _n) {
	assert(T < 6);
	n = _n;
	ord.pb(0); added[0] = 1;
	for(int i = 1; i < n; i++)
		Add(i);
	vector<int> nw = {0};
	for(int i = 1; i < n; i++){
		Find_Edges(nw, ord[i]);
		nw.pb(ord[i]);
	}
}

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