Submission #704343

#	Time	Username	Problem	Language	Result	Execution time	Memory
704343		hollwo_pelw	Park (JOI17_park)	C++17	100 / 100	452 ms	716 KiB

park

#include <bits/stdc++.h>
using namespace std;

#ifndef hollwo_pelw_local
#	include "park.h"
#else
	namespace {
	#define NMAX  1400
	#define DMAX  7
	#define QMAX  45000

	static int T,N,M,Asktotal,Answertotal;
	static int edge_list[NMAX][DMAX];
	static int checked[NMAX][DMAX];
	static int degree[NMAX];
	static int visited[NMAX];
	}

	static void WA(int wa_num) {
		printf("Wrong Answer[%d]\n",wa_num);
		exit(0);
	}
	void Detect(int T, int N);

	void Answer(int A, int B) {
		int i;
		// cout << "! " << A << ' ' << B << '\n';
		if(A < 0||A >= B||B >= N) WA(1);
		for(i = 0 ; i < degree[A] ; i++) {
			if(edge_list[A][i] == B) {
				if(checked[A][i] == 1) WA(3);
				Answertotal++;
				checked[A][i] = 1;
				return;
			}
		}
		WA(2);
	}
	static void dfs(int now, int Place[]) {
		visited[now] = 1;
		int i;
		for(i = 0 ; i < degree[now] ; i++) {
			if(visited[edge_list[now][i]] == 0 && Place[edge_list[now][i]] == 1) dfs(edge_list[now][i], Place);
		}
	}
	int Ask(int A, int B, int Place[]) {
		int i;
		Asktotal++;
		// cout << A << " -> " << B << " : ";
		// for (i = 0; i < N; i++)
		// 	cout << Place[i] << " \n"[i == N - 1];
		if(Asktotal>QMAX) WA(5);
		if(A < 0||A >= B||B >= N) WA(4);
		if(Place[A] != 1) WA(4);
		if(Place[B] != 1) WA(4);
		for(i = 0 ; i < N ; i++) {
			if(Place[i]<0||Place[i]>1) WA(4);
			visited[i] = 0;
		}
		dfs(A, Place);
		// cout << " -> " << visited[B] << "\n";
		return visited[B];
	}
#endif

const int MAXN = 1400;

int n, vs[MAXN], vis[MAXN], p[MAXN];
vector<int> adj[MAXN], reach;

void addedge(int u, int v) {
	adj[u].push_back(v);
	adj[v].push_back(u);
	Answer(min(u, v), max(u, v));
}

void dfs(int u) {
	vs[u] = 1;
	reach.push_back(u);
	for (int v : adj[u])
		if (!vs[v] && vis[v] != 3)
			dfs(v);
}

void find(int u) {
	vis[u] = 2;
	while (true) {
		// if can reach from 0
		for (int i = 0; i < n; i++)
			p[i] = vis[i] == 1;
		p[u] = 1;
		if (Ask(0, u, p)) break;

		int l = 0, r = n - 1;
		while (l < r) {
			int m = (l + r) >> 1;
			for (int i = 0; i < n; i++)
				p[i] = vis[i] == 1 || (!vis[i] && i <= m);
			p[u] = 1;
			if (Ask(0, u, p))
				r = m;
			else
				l = m + 1;
		}
		find(l);
	}

	vector<int> candidate = {0};
	for (int i = 0; i < (int) candidate.size(); i++) {
		int v = candidate[i];
		if (vis[v] == 3) continue;
		
		fill(vs, vs + n, 0);
		reach.clear();

		dfs(v);

		fill(p, p + n, 0);
		for (int x : reach)
			p[x] = 1;
		p[u] = 1;

		if (!Ask(min(u, v), max(u, v), p))
			continue;

		int l = 0, r = reach.size() - 1;
		while (l < r) {
			int m = (l + r) >> 1;
			fill(p, p + n, 0);
			for (int i = 0; i <= m; i++)
				p[reach[i]] = 1;
			p[u] = 1;
			if (Ask(min(u, v), max(u, v), p))
				r = m;
			else
				l = m + 1;
		}

		for (int x : adj[reach[l]])
			candidate.push_back(x);

		addedge(u, reach[l]);
		vis[reach[l]] = 3;
	}

	for (int i = 0; i < n; i++)
		if (vis[i] == 3 || i == u) vis[i] = 1;
}

void Detect(int T, int N) {
	n = N, vis[0] = 1;
	for (int i = 1; i < n; i++)
		if (!vis[i]) find(i);
}

#ifdef hollwo_pelw_local

int main(int argc, char **argv) {
	int i;
	scanf("%d%d%d",&T,&N,&M);
	Answertotal = 0;
	for(i = 0 ; i < N ; i++) degree[i] = 0;
	for(i = 0 ; i < M ; i++) {
		int ea,eb;
		scanf("%d%d",&ea,&eb);
		checked[ea][degree[ea]] =  0;
		checked[eb][degree[eb]] =  0;
		edge_list[ea][degree[ea]++] = eb;
		edge_list[eb][degree[eb]++] = ea;
	}
	Detect(T, N);
	if(Answertotal<M) WA(6);
	printf("Accepted\n");
	return 0;
}

#endif

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