oj.uz

Submission #125343

# Submission time Handle Problem Language Result Execution time Memory
125343 2019-07-05T06:12:49 Z 조승현(#3064) Park (JOI17_park) C++14
67 / 100
 347 ms 22096 KB 
#include "park.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int Place[1400];
vector<int>Tree[1500];
int chk[1500], n;

int Ask2(int a, int b, int *pl) {
	if (a > b)swap(a, b);
	return Ask(a, b, pl);
}

bool cmp(int a, int b) {
	Place[a] = 0;
	int ck = Ask2(0, b, Place);
	Place[a] = 1;
	return ck == 0;
}

int Num[1500], Ed[1500], ord[1500], cnt;

void DFS(int a) {
	Num[a] = ++cnt;
	ord[cnt] = a;
	for (auto &x : Tree[a]) {
		DFS(x);
	}
	Ed[a] = cnt;
}


int FindPar(int a) {
	cnt = 0;
	DFS(0);
	int i;
	int b = 1, e = cnt, mid, r;
	while (b <= e) {
		mid = (b + e) >> 1;
		for (i = 0; i < n; i++)Place[i] = 0;
		for (i = 1; i <= mid; i++) {
			Place[ord[i]] = 1;
		}
		Place[a] = 1;
		if (Ask2(0, a, Place) == 1) {
			r = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	return ord[r];
}

void Do(vector<int>A, vector<int> B) {
	if (B.empty())return;
	int i, sz, j;
	for (auto &x : A)Place[x] = 1;
	sz = B.size();
	for (auto &x : B)Place[x] = 1;
	int pv = 1;
	for (i = 0; i < sz; i++)chk[i] = 0;
	int dest = B[0];
	vector<int>U;
	while (pv < sz) {
		int b = pv, e = sz - 1, r = sz, mid;
		while (b <= e) {
			mid = (b + e) >> 1;
			for (j = pv; j <= mid; j++)Place[B[j]] = 0;
			for (j = mid + 1; j < sz; j++)Place[B[j]] = 1;
			if (Ask2(0, dest, Place) == 0) {
				r = mid;
				e = mid - 1;
			}
			else b = mid + 1;
		}
		if (r != sz) {
			chk[r] = 1;
			U.push_back(B[r]);
			for (j = pv; j <= r; j++)Place[B[j]] = 0;
			Place[B[r]] = 1;
			pv = r + 1;
		}
		else break;
	}
	chk[0] = 1;
	U.push_back(dest);
	vector<int>NA = A, NB;
	for (i = 0; i < sz; i++) {
		if (chk[i])NA.push_back(B[i]);
		else NB.push_back(B[i]);
	}
	for (auto &x : A)Place[x] = 1;
	for (auto &x : B)Place[x] = 0;
	for (auto &x : U)Place[x] = 1;
	sort(U.begin(), U.end(), cmp);

	int pp = FindPar(U[0]);
	Tree[pp].push_back(U[0]);
	for (i = 1; i < U.size(); i++) {
		Tree[U[i - 1]].push_back(U[i]);
	}
	Do(NA, NB);
}

void Detect(int T, int N) {
	n = N;
	int i;
	vector<int>A, B;
	A.push_back(0);
	for (i = 1; i < N; i++) {
		B.push_back(i);
	}
	Do(A, B);
	for (i = 0; i < N; i++) {
		for (auto &x : Tree[i]) {
			Answer(min(i,x), max(i,x));
		}
	}
}

Compilation message

park.cpp: In function 'void Do(std::vector<int>, std::vector<int>)':
park.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 1; i < U.size(); i++) {
              ~~^~~~~~~~~~
park.cpp: In function 'int FindPar(int)':
park.cpp:53:14: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ord[r];
              ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 760 KB Output is correct
2 Correct 288 ms 22096 KB Output is correct
3 Correct 314 ms 13560 KB Output is correct
4 Correct 237 ms 760 KB Output is correct
5 Correct 230 ms 760 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 14244 KB Output is correct
2 Correct 284 ms 15736 KB Output is correct
3 Correct 290 ms 15124 KB Output is correct
4 Correct 282 ms 16716 KB Output is correct
5 Correct 287 ms 13688 KB Output is correct
6 Correct 284 ms 14712 KB Output is correct
7 Correct 274 ms 15448 KB Output is correct
8 Correct 290 ms 15480 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 6908 KB Output is correct
2 Correct 278 ms 11660 KB Output is correct
3 Correct 276 ms 11740 KB Output is correct
4 Correct 210 ms 7288 KB Output is correct
5 Correct 244 ms 8588 KB Output is correct
6 Correct 247 ms 7100 KB Output is correct
7 Correct 208 ms 4776 KB Output is correct
8 Correct 246 ms 10400 KB Output is correct
9 Correct 227 ms 8696 KB Output is correct
10 Correct 248 ms 7800 KB Output is correct
11 Correct 256 ms 8800 KB Output is correct
12 Correct 268 ms 11480 KB Output is correct
13 Correct 207 ms 3992 KB Output is correct
14 Correct 255 ms 10324 KB Output is correct
15 Correct 203 ms 3832 KB Output is correct
16 Correct 290 ms 15352 KB Output is correct
17 Correct 223 ms 696 KB Output is correct
18 Correct 249 ms 9112 KB Output is correct
19 Correct 224 ms 3576 KB Output is correct
20 Correct 238 ms 9400 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 347 ms 11996 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -