oj.uz

Submission #54764

# Submission time Handle Problem Language Result Execution time Memory
54764 2018-07-05T03:03:23 Z spencercompton Park (JOI17_park) C++17
77 / 100
 229 ms 2876 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==1){
		for(int i = 0; i<N; i++){
			place[i] = 0;
		}
		for(int i = 0; i<N; i++){
			for(int j = i+1; j<N; j++){
				place[i] = 1;
				place[j] = 1;
				if(Ask(i,j,place)==1){
					Answer(i,j);
				}
				place[i] = 0;
				place[j] = 0;
			}
		}
		return;
	}
	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;
			int xx = a[0];
			int yy = i;
			if(xx>yy){
				swap(xx,yy);
			}
			if(Ask(xx,yy,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:114:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j<post.size(); j++){
                  ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 8 ms 484 KB Output is correct
3 Correct 8 ms 484 KB Output is correct
4 Correct 8 ms 484 KB Output is correct
5 Correct 8 ms 632 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 892 KB Output is correct
2 Correct 143 ms 900 KB Output is correct
3 Correct 116 ms 2876 KB Output is correct
4 Correct 70 ms 2876 KB Output is correct
5 Correct 81 ms 2876 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 2876 KB Output is correct
2 Correct 206 ms 2876 KB Output is correct
3 Correct 215 ms 2876 KB Output is correct
4 Correct 191 ms 2876 KB Output is correct
5 Correct 216 ms 2876 KB Output is correct
6 Correct 200 ms 2876 KB Output is correct
7 Correct 212 ms 2876 KB Output is correct
8 Correct 207 ms 2876 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 2876 KB Output is correct
2 Correct 229 ms 2876 KB Output is correct
3 Correct 217 ms 2876 KB Output is correct
4 Correct 163 ms 2876 KB Output is correct
5 Correct 178 ms 2876 KB Output is correct
6 Correct 125 ms 2876 KB Output is correct
7 Correct 132 ms 2876 KB Output is correct
8 Correct 205 ms 2876 KB Output is correct
9 Correct 181 ms 2876 KB Output is correct
10 Correct 163 ms 2876 KB Output is correct
11 Correct 172 ms 2876 KB Output is correct
12 Correct 201 ms 2876 KB Output is correct
13 Correct 132 ms 2876 KB Output is correct
14 Correct 185 ms 2876 KB Output is correct
15 Correct 127 ms 2876 KB Output is correct
16 Correct 207 ms 2876 KB Output is correct
17 Correct 68 ms 2876 KB Output is correct
18 Correct 177 ms 2876 KB Output is correct
19 Correct 115 ms 2876 KB Output is correct
20 Correct 187 ms 2876 KB Output is correct

Subtask #5
0 / 23.0

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