oj.uz

Submission #125360

# Submission time Handle Problem Language Result Execution time Memory
125360 2019-07-05T06:53:13 Z 조승현(#3064) Park (JOI17_park) C++14
100 / 100
 474 ms 22116 KB 
#include "park.h"
#include <cstdio>
#include <algorithm>
#include <vector>
#define pii pair<int,int>
using namespace std;

int Place[1400], vis[1500], cant[1500], cur[1500];
vector<int>G[1500];
int chk[1500], n;

int Ask2(int a, int b, int *pl) {
	if (a > b)swap(a, b);
	return Ask(a, b, pl);
}
void Add_Edge(int a, int b) {
	G[a].push_back(b);
	G[b].push_back(a);
}

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) {
	vis[a] = 1;
	Num[a] = ++cnt;
	ord[cnt] = a;
	for (auto &x : G[a]) {
		if(!vis[x] && cur[x])DFS(x);
	}
	Ed[a] = cnt;
}


vector<pii>TT;
vector<int>AA;

void DFS2(int a) {
	vis[a] = 1;
	AA.push_back(a);
	for (auto &x : G[a]) {
		if (!vis[x] && cur[x]) {
			DFS2(x);
		}
	}
}

void FindPar(vector<int> V, int a, int CK) {
	if (V.empty())return;
	int i;
	for (i = 0; i < n; i++)cur[i] = vis[i] = 0;
	for (auto &x : V)cur[x] = 1;
	cnt = 0;
	int rt = V[0];
	DFS(rt);
	if (CK) {
		for (i = 0; i < n; i++)Place[i] = 0;
		for (auto &x : V)Place[x] = 1;
		Place[a] = 1;
		if (!Ask2(rt, a, Place))return;
	}
	int b = 1, e = cnt, mid, r = cnt + 1;
	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(rt, a, Place) == 1) {
			r = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	if (r > cnt)return;
	int y = ord[r];
	TT.push_back({ y, a });
	for (i = 0; i < n; i++)vis[i] = 0;
	cur[y] = 0;
	vector<vector<int>>VV;
	for (auto &t : G[y]) {
		if (!vis[t] && cur[t]) {
			AA.clear();
			DFS2(t);
			VV.push_back(AA);
		}
	}
	for (auto &t : VV) {
		FindPar(t, a, 1);
	}
}

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);
	TT.clear();
	FindPar(A, U[0], 0);
	for (auto &t : TT) {
		Add_Edge(t.first, t.second);
	}
	for (i = 1; i < U.size(); i++) {
		Add_Edge(U[i - 1], 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 : G[i]) {
			if (i < x)Answer(i, x);
		}
	}
}

Compilation message

park.cpp: In function 'void Do(std::vector<int>, std::vector<int>)':
park.cpp:147:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 1; i < U.size(); i++) {
              ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 12 ms 888 KB Output is correct
3 Correct 11 ms 888 KB Output is correct
4 Correct 27 ms 1016 KB Output is correct
5 Correct 54 ms 1144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 816 KB Output is correct
2 Correct 350 ms 22116 KB Output is correct
3 Correct 335 ms 13676 KB Output is correct
4 Correct 239 ms 756 KB Output is correct
5 Correct 236 ms 752 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 14220 KB Output is correct
2 Correct 351 ms 15676 KB Output is correct
3 Correct 348 ms 15096 KB Output is correct
4 Correct 341 ms 16600 KB Output is correct
5 Correct 348 ms 13724 KB Output is correct
6 Correct 336 ms 14840 KB Output is correct
7 Correct 358 ms 15660 KB Output is correct
8 Correct 356 ms 15224 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 7040 KB Output is correct
2 Correct 332 ms 11620 KB Output is correct
3 Correct 328 ms 11624 KB Output is correct
4 Correct 237 ms 7308 KB Output is correct
5 Correct 281 ms 8696 KB Output is correct
6 Correct 276 ms 7192 KB Output is correct
7 Correct 233 ms 4856 KB Output is correct
8 Correct 291 ms 10488 KB Output is correct
9 Correct 262 ms 8704 KB Output is correct
10 Correct 286 ms 8036 KB Output is correct
11 Correct 299 ms 8836 KB Output is correct
12 Correct 323 ms 11616 KB Output is correct
13 Correct 223 ms 4088 KB Output is correct
14 Correct 310 ms 10592 KB Output is correct
15 Correct 218 ms 3840 KB Output is correct
16 Correct 351 ms 15224 KB Output is correct
17 Correct 225 ms 764 KB Output is correct
18 Correct 288 ms 9156 KB Output is correct
19 Correct 240 ms 3704 KB Output is correct
20 Correct 279 ms 9208 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 11948 KB Output is correct
2 Correct 452 ms 13076 KB Output is correct
3 Correct 400 ms 14584 KB Output is correct
4 Correct 313 ms 8968 KB Output is correct
5 Correct 474 ms 14396 KB Output is correct
6 Correct 222 ms 2484 KB Output is correct
7 Correct 349 ms 8952 KB Output is correct
8 Correct 288 ms 7288 KB Output is correct
9 Correct 292 ms 8048 KB Output is correct
10 Correct 340 ms 11252 KB Output is correct
11 Correct 293 ms 8688 KB Output is correct
12 Correct 324 ms 8960 KB Output is correct
13 Correct 295 ms 10360 KB Output is correct
14 Correct 451 ms 12792 KB Output is correct
15 Correct 357 ms 10620 KB Output is correct
16 Correct 351 ms 14844 KB Output is correct
17 Correct 217 ms 704 KB Output is correct
18 Correct 327 ms 10244 KB Output is correct