oj.uz

Submission #54760

# Submission time Handle Problem Language Result Execution time Memory
54760 2018-07-05T02:56:41 Z spencercompton Park (JOI17_park) C++17
0 / 100
 28 ms 2040 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
bool in[1400];

static int place[1400];
vector<int> post;
vector<int> adj[1400];
vector<bool> v;
int n;
void dfs(int now){
	v[now] = true;
	post.push_back(now);
	for(int i = 0; i<adj[now].size(); i++){
		int to = adj[now][i];
		if(!v[to]){
			dfs(to);
		}
	}
}
void from(int a, int b){
	if(b<a){
		swap(a,b);
	}
	// cout << "FROM " << a << " " << b << endl;
	for(int i = 0; i<n; i++){
		place[i] = 0;
	}
	place[a] = 1;
	place[b] = 1;
	// cout << "P1 " << a << " " << b << endl;
	// for(int i = 0; i<n; i++){
	// 	cout << place[i] << " " ;
	// }
	// cout << endl;
	if(Ask(a,b,place)==1){
		// cout << "OK " << endl;
		Answer(a,b);
		in[a] = true;
		in[b] = true;
		adj[a].push_back(b);
		adj[b].push_back(a);
		return;
	}
	// cout << "NOPE " << endl;
	vector<int> outside;
	for(int i = 0; i<n; i++){
		if(!in[i] && i!=a && i!=b){
			outside.push_back(i);
		}
	}
	int low = 0;
	int high = (int)outside.size()-1;
	while(low<high){
		int mid = (low+high)/2;
		for(int i = 0; i<n; i++){
			place[i] = 1;
		}
		for(int i = 0; i<=mid; i++){
			place[outside[i]] = 1;
		}
		for(int i = mid+1; i<(int)outside.size(); i++){
			place[outside[i]] = 0;
		}
		if(Ask(a,b,place)==1){
			high = mid;
		}
		else{
			low = mid+1;
		}
	}
	from(a,outside[low]);
	from(outside[low],b);
}
void Detect(int T, int N) {
	if(T==5){
		return;
	}
	n = N;
	for(int i = 0; i<N; i++){
		place[i] = 0;
	}
	for(int i = 0; i<N; i++){
		in[i] = false;
	}
	in[0] = true;
	for(int i = 1; i<N; i++){
		// cout << "X " << i << " " << N << endl;
		if(in[i]){
			continue;
		}
		v.clear();
		v.resize(N);
		post.clear();
		dfs(0);
		vector<int> possible;
		for(int j = 0; j<post.size(); j++){
			possible.push_back(post[j]);
		}
		// cout << "A " << endl;
		// for(int j = 0; j<(int)possible.size(); j++){
		// 	cout << possible[j] << " " ;
		// }
		// cout << "B "<< endl;
		while(possible.size()>1){
			vector<int> a;
			vector<int> b;
			for(int j = 0; j<N; j++){
				place[j] = 1;
			}
			for(int j = 0; j<(int)possible.size()/2; j++){
				a.push_back(possible[j]);
			}
			for(int j = (int)possible.size()/2; j<(int)possible.size(); j++){
				b.push_back(possible[j]);
				place[possible[j]] = 0;
			}
			// cout << "BEF " << endl;
			// for(int j = 0; j<a.size(); j++){
			// 	cout << a[j] << " ";
			// }
			// cout << endl;
			// for(int j = 0; j<b.size(); j++){
			// 	cout << b[j] << " ";
			// }
			// cout << endl;
			// for(int j = 0; j<N; j++){
			// 	cout << place[j] << " ";
			// }
			// cout << endl;
			if(Ask(a[0],i,place)==1){
				possible = a;
			}
			else{
				possible = b;
			}
			// cout << "AFT " << endl;
		}
		assert((int)possible.size()==1);
		from(possible[0],i);
	}
}

Compilation message

park.cpp: In function 'void dfs(int)':
park.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<adj[now].size(); i++){
                 ~^~~~~~~~~~~~~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<post.size(); j++){
                  ~^~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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