oj.uz

Submission #60411

# Submission time Handle Problem Language Result Execution time Memory
60411 2018-07-24T06:48:32 Z 김세빈(#1743) Park (JOI17_park) C++11
77 / 100
 475 ms 932 KB 
#include "park.h"

#include <bits/stdc++.h>

using namespace std;

static int P[1400];
static vector <int> K[1500];
static bool chk[1500];
static int n, d;

bool ask(int a, int b, vector <int> &V, int l, int r)
{
	int i;
	
	for(i=0; i<n; i++) P[i] = 1;
	for(i=l; i<=r; i++) P[V[i]] = 0;
	
	if(a > b) swap(a, b);
	
	return Ask(a, b, P);
}

bool check_dep(int k, int p)
{
	int i;
	
	for(i=0; i<n; i++) P[i] = 0;
	for(i=0; i<=k; i++){
		for(int t: K[i]) P[t] = 1;
	}
	P[p] = 1;
	
	return Ask(0, p, P);
}

int f(int p, vector <int> &V, int s, int e)
{
	if(s == e) return V[s];
	int m = s + e >> 1;
	if(ask(0, p, V, s, m)) return f(p, V, m+1, e);
	else return f(p, V, s, m);
}

int find_one_parent(int p)
{
	vector <int> V;
	int i;
	
	for(i=0; i<n; i++){
		if(!chk[i]) V.push_back(i);
	}
	
	if(ask(0, p, V, 0, V.size() - 1)) return -1;
	
	return f(p, V, 0, V.size() - 1);
}

void connect(int p)
{
	int k, s, e, mid;
	
	chk[p] = 1;
	
	for(; ; ){
		k = find_one_parent(p);
		if(k == -1) break;
		else connect(k);
	}
	
	for(s=0, e=d-1; s<=e; ){
		mid = s+e >> 1;
		if(check_dep(mid, p)) e = mid - 1;
		else s = mid + 1;
	}
	
	k = f(p, K[e + 1], 0, K[e + 1].size() - 1);
	Answer(min(k, p), max(k, p));
	
	if(e + 2 > d) d ++;
	K[e + 2].push_back(p);
}

void Detect(int T, int N)
{
	n = N;
	
	if(T == 1){
		int i, j, k;
		
		for(i=0; i<n; i++){
			for(j=i+1; j<n; j++){
				for(k=0; k<n; k++) P[k] = 0;
				P[i] = P[j] = 1;
				if(Ask(i, j, P)) Answer(i, j);
			}
		}
		
		return;
	}
	
	int i;
	
	chk[0] = 1;
	K[0].push_back(0);
	
	for(i=1; i<n; i++){
		if(!chk[i]) connect(i);
	}
}

Compilation message

park.cpp: In function 'int f(int, std::vector<int>&, int, int)':
park.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
park.cpp: In function 'void connect(int)':
park.cpp:72:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = s+e >> 1;
         ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 22 ms 376 KB Output is correct
3 Correct 16 ms 416 KB Output is correct
4 Correct 15 ms 488 KB Output is correct
5 Correct 16 ms 488 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 904 KB Output is correct
2 Correct 147 ms 904 KB Output is correct
3 Correct 225 ms 904 KB Output is correct
4 Correct 454 ms 932 KB Output is correct
5 Correct 454 ms 932 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 932 KB Output is correct
2 Correct 360 ms 932 KB Output is correct
3 Correct 400 ms 932 KB Output is correct
4 Correct 354 ms 932 KB Output is correct
5 Correct 475 ms 932 KB Output is correct
6 Correct 394 ms 932 KB Output is correct
7 Correct 387 ms 932 KB Output is correct
8 Correct 395 ms 932 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 932 KB Output is correct
2 Correct 426 ms 932 KB Output is correct
3 Correct 392 ms 932 KB Output is correct
4 Correct 373 ms 932 KB Output is correct
5 Correct 407 ms 932 KB Output is correct
6 Correct 316 ms 932 KB Output is correct
7 Correct 373 ms 932 KB Output is correct
8 Correct 389 ms 932 KB Output is correct
9 Correct 417 ms 932 KB Output is correct
10 Correct 406 ms 932 KB Output is correct
11 Correct 374 ms 932 KB Output is correct
12 Correct 420 ms 932 KB Output is correct
13 Correct 420 ms 932 KB Output is correct
14 Correct 360 ms 932 KB Output is correct
15 Correct 359 ms 932 KB Output is correct
16 Correct 337 ms 932 KB Output is correct
17 Correct 469 ms 932 KB Output is correct
18 Correct 394 ms 932 KB Output is correct
19 Correct 399 ms 932 KB Output is correct
20 Correct 412 ms 932 KB Output is correct

Subtask #5
0 / 23.0

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