oj.uz

답안 #704345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
704345 2023-03-02T04:01:58 Z vjudge1 Park (JOI17_park) C++17
100 / 100
 442 ms 668 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 380 KB Output is correct
3 Correct 7 ms 340 KB Output is correct
4 Correct 24 ms 388 KB Output is correct
5 Correct 66 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 668 KB Output is correct
2 Correct 139 ms 488 KB Output is correct
3 Correct 174 ms 488 KB Output is correct
4 Correct 436 ms 628 KB Output is correct
5 Correct 435 ms 656 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 456 KB Output is correct
2 Correct 213 ms 444 KB Output is correct
3 Correct 222 ms 468 KB Output is correct
4 Correct 193 ms 428 KB Output is correct
5 Correct 240 ms 432 KB Output is correct
6 Correct 221 ms 552 KB Output is correct
7 Correct 216 ms 428 KB Output is correct
8 Correct 215 ms 480 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 544 KB Output is correct
2 Correct 260 ms 440 KB Output is correct
3 Correct 262 ms 432 KB Output is correct
4 Correct 303 ms 572 KB Output is correct
5 Correct 326 ms 452 KB Output is correct
6 Correct 308 ms 628 KB Output is correct
7 Correct 321 ms 448 KB Output is correct
8 Correct 269 ms 444 KB Output is correct
9 Correct 267 ms 472 KB Output is correct
10 Correct 310 ms 500 KB Output is correct
11 Correct 324 ms 608 KB Output is correct
12 Correct 265 ms 448 KB Output is correct
13 Correct 345 ms 480 KB Output is correct
14 Correct 299 ms 484 KB Output is correct
15 Correct 360 ms 468 KB Output is correct
16 Correct 228 ms 560 KB Output is correct
17 Correct 436 ms 548 KB Output is correct
18 Correct 302 ms 568 KB Output is correct
19 Correct 385 ms 592 KB Output is correct
20 Correct 281 ms 460 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 322 ms 472 KB Output is correct
2 Correct 299 ms 592 KB Output is correct
3 Correct 246 ms 472 KB Output is correct
4 Correct 315 ms 484 KB Output is correct
5 Correct 298 ms 468 KB Output is correct
6 Correct 401 ms 500 KB Output is correct
7 Correct 329 ms 608 KB Output is correct
8 Correct 349 ms 456 KB Output is correct
9 Correct 324 ms 480 KB Output is correct
10 Correct 263 ms 444 KB Output is correct
11 Correct 312 ms 496 KB Output is correct
12 Correct 321 ms 452 KB Output is correct
13 Correct 278 ms 432 KB Output is correct
14 Correct 319 ms 488 KB Output is correct
15 Correct 286 ms 460 KB Output is correct
16 Correct 218 ms 572 KB Output is correct
17 Correct 442 ms 548 KB Output is correct
18 Correct 273 ms 508 KB Output is correct