Submission #1073452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073452		AdamGS	Park (JOI17_park)	C++17	67 / 100	73 ms	2140 KiB

park

#include "park.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1407;
static int Place[1400];
vector<int>V[LIM], pos, ord;
int odw[LIM], oc[LIM], usun[LIM], n, ile;
void DFS(int x, int o) {
	for(auto i : V[x]) if(i!=o) DFS(i, x);
	pos.pb(x);
}
int znajdz_ojca(int x) {
	pos.clear();
	DFS(0, 0);
	reverse(all(pos));
	int po=0, ko=(int)pos.size()-1;
	while(po<ko) {
		int sr=(po+ko)/2;
		rep(i, n) Place[i]=0;
		rep(i, sr+1) Place[pos[i]]=1;
		rep(i, n) if(!odw[i]) Place[i]=1;
		if(Ask(0, x, Place)) ko=sr; else po=sr+1;
	}
	return pos[po];
}
void sciezka(int a, int b) {
	rep(i, n) Place[i]=0;
	Place[a]=Place[b]=1;
	if(Ask(min(a, b), max(a, b), Place)) {
		odw[b]=1; ++ile;
		V[a].pb(b);
		V[b].pb(a);
		Answer(min(a, b), max(a, b));
		return;
	}
	vector<int>T;
	rep(i, n) if(!odw[i] && i!=b) T.pb(i);
	int po=0, ko=(int)T.size()-1;
	while(po<ko) {
		int sr=(po+ko)/2;
		rep(i, n) Place[i]=0;
		rep(i, sr+1) Place[T[i]]=1;
		Place[a]=Place[b]=1;
		if(Ask(min(a, b), max(a, b), Place)) ko=sr; else po=sr+1;
	}
	sciezka(a, T[po]);
	sciezka(T[po], b);
}
void DFS2(int x, int o) {
	oc[x]=o;
	for(auto i : V[x]) if(i!=o) DFS2(i, x);
}
void DFS4(int x) {
	if(usun[x]) return;
	ord.pb(x);
	for(auto i : V[x]) if(i!=oc[x]) DFS4(i);
}
void DFS3(int x, int p) {
	for(auto i : V[x]) if(i!=oc[x]) {
		while(true) {
			ord.clear();
			DFS4(i);
			if(ord.size()==0) break;
			rep(j, n) Place[j]=0;
			Place[p]=1;
			for(auto j : ord) Place[j]=1;
			if(!Ask(min(p, ord[0]), max(p, ord[0]), Place)) break;
			int po=0, ko=ord.size()-1;
			while(po<ko) {
				int sr=(po+ko)/2;
				rep(j, n) Place[j]=0;
				Place[p]=1;
				rep(j, sr+1) Place[ord[j]]=1;
				if(Ask(min(p, ord[0]), max(p, ord[0]), Place)) ko=sr; else po=sr+1;
			}
			usun[ord[po]]=1;
			if(p<ord[po]) Answer(p, ord[po]);
			DFS3(ord[po], p);
		}
	}
}
void Detect(int T, int N) {
	n=N;
	odw[0]=ile=1;
	while(ile<n) {
		int x=-1;
		rep(i, n) if(!odw[i]) {
			x=i;
			break;
		}
		int p=znajdz_ojca(x);
		sciezka(p, x);
	}
	rep(a, n) {
		a=1;
		DFS2(a, a);
		rep(b, n) usun[b]=0;
		for(auto b : V[a]) usun[b]=1;
		for(auto b : V[a]) DFS3(b, a);
		break;
	}
}

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