oj.uz

Submission #125319

# Submission time Handle Problem Language Result Execution time Memory
125319 2019-07-05T05:36:54 Z khsoo01 Park (JOI17_park) C++11
10 / 100
 430 ms 1144 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[S] = true;
	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;
		preorder(0, -1, V);
		for(int j=0;j<n;j++) {
			place[j] = 1;
		}
		int M = Find(0, i, V);
		V.clear();
		for(int j=0;j<n;j++) {
			if(tree[j].empty()) V.push_back(j);
		}
		for(int j=0;j<n;j++) {
			place[j] = 0;
		}
		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:92:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<X.size();j++) {
               ~^~~~~~~~~
park.cpp:95:7: warning: 'I' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int I;
       ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1144 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 812 KB Output is correct
2 Correct 235 ms 692 KB Output is correct
3 Correct 195 ms 768 KB Output is correct
4 Correct 149 ms 632 KB Output is correct
5 Correct 148 ms 904 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 430 ms 912 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 788 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 419 ms 888 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -