oj.uz

Submission #704343

# Submission time Handle Problem Language Result Execution time Memory
704343 2023-03-02T04:01:12 Z hollwo_pelw Park (JOI17_park) C++17
100 / 100
 452 ms 716 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 340 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 25 ms 384 KB Output is correct
5 Correct 69 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 500 KB Output is correct
2 Correct 130 ms 484 KB Output is correct
3 Correct 175 ms 620 KB Output is correct
4 Correct 435 ms 648 KB Output is correct
5 Correct 450 ms 716 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 464 KB Output is correct
2 Correct 215 ms 468 KB Output is correct
3 Correct 238 ms 440 KB Output is correct
4 Correct 199 ms 548 KB Output is correct
5 Correct 249 ms 428 KB Output is correct
6 Correct 225 ms 448 KB Output is correct
7 Correct 212 ms 444 KB Output is correct
8 Correct 220 ms 436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 556 KB Output is correct
2 Correct 264 ms 440 KB Output is correct
3 Correct 282 ms 488 KB Output is correct
4 Correct 298 ms 460 KB Output is correct
5 Correct 320 ms 476 KB Output is correct
6 Correct 345 ms 644 KB Output is correct
7 Correct 319 ms 596 KB Output is correct
8 Correct 283 ms 464 KB Output is correct
9 Correct 287 ms 460 KB Output is correct
10 Correct 327 ms 468 KB Output is correct
11 Correct 332 ms 472 KB Output is correct
12 Correct 263 ms 468 KB Output is correct
13 Correct 366 ms 496 KB Output is correct
14 Correct 286 ms 508 KB Output is correct
15 Correct 369 ms 588 KB Output is correct
16 Correct 221 ms 580 KB Output is correct
17 Correct 431 ms 556 KB Output is correct
18 Correct 291 ms 516 KB Output is correct
19 Correct 377 ms 484 KB Output is correct
20 Correct 283 ms 588 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 568 KB Output is correct
2 Correct 300 ms 616 KB Output is correct
3 Correct 245 ms 492 KB Output is correct
4 Correct 309 ms 476 KB Output is correct
5 Correct 299 ms 472 KB Output is correct
6 Correct 394 ms 468 KB Output is correct
7 Correct 336 ms 552 KB Output is correct
8 Correct 332 ms 480 KB Output is correct
9 Correct 330 ms 644 KB Output is correct
10 Correct 260 ms 512 KB Output is correct
11 Correct 283 ms 648 KB Output is correct
12 Correct 309 ms 468 KB Output is correct
13 Correct 271 ms 456 KB Output is correct
14 Correct 304 ms 476 KB Output is correct
15 Correct 286 ms 484 KB Output is correct
16 Correct 216 ms 464 KB Output is correct
17 Correct 430 ms 568 KB Output is correct
18 Correct 266 ms 528 KB Output is correct