oj.uz

Submission #125325

# Submission time Handle Problem Language Result Execution time Memory
125325 2019-07-05T05:45:18 Z khsoo01 Park (JOI17_park) C++11
100 / 100
 314 ms 804 KB 
#include<bits/stdc++.h>
#include "park.h"
using namespace std;

namespace {
	const int N = 1505;
	int place[N];
	bool vis[N], blk[N];

	int n;
	vector<int> tree[N];
}

int check (int S, int E, vector<int> &O) {
	for(int i=0;i<n;i++) place[i] = 0;
	for(auto &T : O) place[T] = 1;
	place[S] = 1;
	place[E] = 1;
	return Ask(min(S, E), max(S, E), place);
}

int Find (int A, int B, vector<int> &O) {
	int S = 0, E = O.size();
	while(S<E) {
		int M = (S+E)/2;
		vector<int> V;
		for(int i=0;i<M;i++) {
			V.push_back(O[i]);
		}
		check(A, B, V) ? E = M : S = M+1;
	}
	return (S ? O[S-1] : A);
}

void preorder (int C, int P, vector<int> &O) {
	O.push_back(C);
	for(auto &T: tree[C]) {
		if(T == P || blk[T]) continue;
		preorder(T, C, O);
	}
}

void construct (int S, int E, vector<int> &O) {
	vis[E] = true;
	int M = Find(S, E, O);
	if(M == S) {
		tree[S].push_back(E);
		tree[E].push_back(S);
		Answer(min(S, E), max(S, E));
	}
	else {
		construct(S, M, O);
		construct(M, E, O);
	}
}

void Try (int P, int I) {
	vector<int> V;
	preorder(I, -1, V);
	if(!check(I, P, V)) return;
	int J = Find(I, P, V);
	Answer(min(P, J), max(P, J));
	blk[J] = true;
	for(auto &T : tree[J]) {
		if(!blk[T]) Try(P, T);
	}
}

void Detect (int T, int N) {
	n = N;
	for(int i=1;i<n;i++) {
		if(vis[i]) continue;
		vector<int> V;
		for(int j=1;j<n;j++) {
			if(tree[j].empty()) V.push_back(j);
		}
		preorder(0, -1, V);
		int M = Find(0, i, V);
		if(tree[M].empty()) M = 0;
		V.clear();
		for(int j=1;j<n;j++) {
			if(tree[j].empty()) V.push_back(j);
		}
		construct(M, i, V);
	}
	vector<int> X;
	preorder(0, -1, X);
	for(int i=(int)X.size()-1;i>0;i--) {
		for(int j=0;j<X.size();j++) {
			blk[X[j]] = (j >= i);
		}
		int I;
		for(auto &T : tree[X[i]]) {
			if(!blk[T]) {I = T; break;}
		}
		blk[I] = true;
		for(auto &T : tree[I]) {
			if(!blk[T]) Try(X[i], T);
		}
	}
}

Compilation message

park.cpp: In function 'void Detect(int, int)':
park.cpp:89:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<X.size();j++) {
               ~^~~~~~~~~
park.cpp:92:7: warning: 'I' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int I;
       ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Correct 11 ms 432 KB Output is correct
3 Correct 10 ms 404 KB Output is correct
4 Correct 18 ms 376 KB Output is correct
5 Correct 29 ms 584 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 724 KB Output is correct
2 Correct 305 ms 696 KB Output is correct
3 Correct 236 ms 732 KB Output is correct
4 Correct 150 ms 632 KB Output is correct
5 Correct 148 ms 632 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 552 KB Output is correct
2 Correct 257 ms 632 KB Output is correct
3 Correct 267 ms 632 KB Output is correct
4 Correct 260 ms 652 KB Output is correct
5 Correct 253 ms 760 KB Output is correct
6 Correct 279 ms 684 KB Output is correct
7 Correct 256 ms 504 KB Output is correct
8 Correct 255 ms 632 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 520 KB Output is correct
2 Correct 243 ms 692 KB Output is correct
3 Correct 241 ms 632 KB Output is correct
4 Correct 191 ms 576 KB Output is correct
5 Correct 228 ms 680 KB Output is correct
6 Correct 197 ms 604 KB Output is correct
7 Correct 159 ms 716 KB Output is correct
8 Correct 229 ms 716 KB Output is correct
9 Correct 202 ms 504 KB Output is correct
10 Correct 241 ms 716 KB Output is correct
11 Correct 247 ms 632 KB Output is correct
12 Correct 248 ms 504 KB Output is correct
13 Correct 169 ms 604 KB Output is correct
14 Correct 253 ms 712 KB Output is correct
15 Correct 165 ms 656 KB Output is correct
16 Correct 255 ms 632 KB Output is correct
17 Correct 164 ms 760 KB Output is correct
18 Correct 240 ms 620 KB Output is correct
19 Correct 172 ms 632 KB Output is correct
20 Correct 222 ms 576 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 804 KB Output is correct
2 Correct 276 ms 616 KB Output is correct
3 Correct 266 ms 504 KB Output is correct
4 Correct 247 ms 672 KB Output is correct
5 Correct 314 ms 644 KB Output is correct
6 Correct 168 ms 632 KB Output is correct
7 Correct 231 ms 668 KB Output is correct
8 Correct 233 ms 640 KB Output is correct
9 Correct 239 ms 632 KB Output is correct
10 Correct 234 ms 504 KB Output is correct
11 Correct 214 ms 716 KB Output is correct
12 Correct 199 ms 632 KB Output is correct
13 Correct 231 ms 596 KB Output is correct
14 Correct 276 ms 632 KB Output is correct
15 Correct 243 ms 632 KB Output is correct
16 Correct 251 ms 504 KB Output is correct
17 Correct 162 ms 632 KB Output is correct
18 Correct 261 ms 632 KB Output is correct