oj.uz

Submission #125338

# Submission time Handle Problem Language Result Execution time Memory
125338 2019-07-05T05:53:41 Z 조승현(#3064) Park (JOI17_park) C++14
0 / 100
 204 ms 632 KB 
#include "park.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

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

bool cmp(int a, int b) {
	Place[a] = 0;
	int ck = Ask(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 (Ask(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 (Ask(0, dest, Place) == 0) {
				r = mid;
				e = mid - 1;
			}
			else b = mid + 1;
		}
		if (r != sz) {
			chk[r] = 1;
			U.push_back(B[r]);
			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(i, x);
	}
}

Compilation message

park.cpp: In function 'void Do(std::vector<int>, std::vector<int>)':
park.cpp:94: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:48: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[2]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 504 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 532 KB Wrong Answer[4]
2 Halted 0 ms 0 KB -