Submission #25884

#	Time	Username	Problem	Language	Result	Execution time	Memory
25884		youaremysky99	Park (JOI17_park)	C++14	67 / 100	386 ms	10140 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];
int asked = 0;
int banned[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] && !banned[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; 
		For(i,0,mid) place[other[i]] = 1;
		Rep(i,N) if (banned[i]) place[i] = 0;
		place[s] = place[t] = 1;
		++asked;
		if (Ask(min(s,t), max(s,t) ,place)) {			
			id = mid;
			r = mid - 1;
		} else l = mid + 1;
	} 

	return other[id];
}	

bool needAsk[maxn][maxn];
bool haveEdge(int s, int t) {
	if (needAsk[s][t]) return false;
	if (s == t) return false;
	if (edge[s][t]) return 1;
	memset(place,0,sizeof(place));
	place[s] = place[t] = 1;
	++asked;
	if (Ask(min(s,t),max(s,t),place)) {
		edge[s][t] = edge[t][s] = 1;
		V[s].push_back(t); V[t].push_back(s);
		return 1;
	}
	needAsk[s][t] = needAsk[t][s] = true;
	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;
int par[maxn];
void dfs(int u) {
	was[u] = true;
	num[u] = ++top;
	for (int v : V[u]) if (!was[v]) dfs(v), par[v] = u;
}

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);
}

#include <queue>
void Detect(int T, int _N) {
	N = _N;
	memset(edge,0,sizeof(edge));
	memset(banned,0,sizeof(banned));

	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);
	}

	
	if (T == 5 || T == 1) {
		Rep(i,N) {
			if (edge[i][0] || i == 0) {
				int deg = 0;
				Rep(j,N) deg += edge[i][j];
				while (deg < 7) {
					Rep(j,N) if (haveEdge(i,j)) {
						++deg;
					}
				}
			}
		}

		memset(used,0,sizeof(used));
		For(i,1, N - 1) if (!edge[i][0]) {
			int deg = 0;
			Rep(j,N) if (edge[i][j]) ++deg;
			queue<int> qu; 
			qu.push(0);
			
			bool rooted[maxn];
			memset(rooted,false,sizeof(rooted));
			while (sz(qu) && deg < 7) {
				int root = qu.front(); qu.pop(); rooted[root] = true;
				if (haveEdge(i,root)) {
					for (int j : V[root]) if (j != i && !rooted[j]) {
						qu.push(j);
					}
				} else {
					memset(used,0,sizeof(used));
					memset(banned,0,sizeof(banned));
					Rep(j,N) if (edge[i][j]) banned[j] = true;
					top = 0;
					memset(was,false,sizeof(was));
					dfs(root);
					int x = findFirst(i,root,used,true);
					if (haveEdge(i,x) && !rooted[x]) {
						qu.push(x);
					}
				}
				deg = 0;
				Rep(j,N) if (edge[i][j]) ++deg;
			}
		}
	}  

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

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