Submission #25880

#	Time	Username	Problem	Language	Result	Execution time	Memory
25880		youaremysky99	Park (JOI17_park)	C++14	0 / 100	3 ms	6084 KiB

park

#include "park.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
#define For(i,a,b) for (int i = (a), _b = (b); i <= _b; ++i)
#define Rep(i,a) for (int i = 0, _a = (a); i < _a; i++) 
#define sz(a) ((int)a.size())

const int maxn = 2000;
int place[maxn];
int N;
vector<int> V[maxn];

/// Ask(int a, int b, int place[]), 0-based
/// use Answer(int a, int b) for an edge

vector<int> path;
bool used[maxn];
bool edge[maxn][maxn];
int num[maxn];

bool cmp(int i, int j) {
	return num[i] > num[j];
}

int findFirst(int s, int t, bool used[], bool needtoSort = false) {
	if (s == t) return N + 1;
	vector<int> other;
	Rep(i,N) if (!used[i]) other.push_back(i);
	if (needtoSort) {
		sort(other.begin(), other.end(), cmp);
	}
	if (sz(other) == 0) return N + 1;
	int l = 0, r = sz(other) - 1, id = sz(other) - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;

		memset(place,0,sizeof(place));
		Rep(i,N) if (used[i]) place[i] = 1; place[s] = place[t] = 1;
		For(i,0,mid) place[other[i]] = 1;
		
		if (Ask(min(s,t), max(s,t) ,place)) {
			id = mid;
			r = mid - 1;
		} else l = mid + 1;
	} 

	return other[id];
}	

bool haveEdge(int s, int t) {
	if (edge[s][t]) return 1;
	memset(place,0,sizeof(place));
	place[s] = place[t] = 1;
	if (Ask(s,t,place)) {
		edge[s][t] = edge[t][s] = 1;
		V[s].push_back(t); V[t].push_back(s);
		return 1;
	}
	return 0;
}

void doFirst(int s, int t) {
	if (haveEdge(s,t)) return;

	memset(used,0,sizeof(used)); used[s] = used[t] = 1;
	int x = findFirst(s,t,used);
	doFirst(s,x);
	doFirst(x,t);
}

bool was[maxn]; 
int top = 0;
void dfs(int u) {
	was[u] = true;
	num[u] = ++top;
	for (int v : V[u]) if (!was[v]) dfs(v);
}

void doSecond(int s, int t, bool was[]) {
	if (!haveEdge(s,t)) {
		memset(used,0,sizeof(used));
		Rep(i,N) if (!was[i]) used[i] = true; used[s] = used[t] = 1;
		int x = findFirst(s,t,used,true);
		doFirst(x,t);
	}

	Rep(i,N) was[i] = false;
	memset(num,0,sizeof(num));
	top = 0;
	dfs(0);
}

void Detect(int T, int _N) {
	N = _N;
	memset(edge,0,sizeof(edge));

	doFirst(0,1);
	memset(was,0,sizeof(was));
	memset(num,0,sizeof(num));
	top = 0;
	dfs(0);

	
	For(i,2,N - 1) if (!was[i]) {
		doSecond(0,i,was);
	}

	Rep(u,N) Rep(v,N) if (u < v) if (edge[u][v]) Answer(u,v);
}

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