Submission #1072551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072551		AdamGS	Park (JOI17_park)	C++17	67 / 100	78 ms	1880 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;
int odw[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 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);
	}
}

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