oj.uz

답안 #60410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
60410 2018-07-24T06:46:39 Z 김세빈(#1743) Park (JOI17_park) C++11
67 / 100
 470 ms 1680 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;
	
	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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 748 KB Output is correct
2 Correct 149 ms 836 KB Output is correct
3 Correct 247 ms 904 KB Output is correct
4 Correct 426 ms 904 KB Output is correct
5 Correct 427 ms 904 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 330 ms 904 KB Output is correct
2 Correct 347 ms 932 KB Output is correct
3 Correct 414 ms 932 KB Output is correct
4 Correct 371 ms 932 KB Output is correct
5 Correct 430 ms 932 KB Output is correct
6 Correct 372 ms 932 KB Output is correct
7 Correct 338 ms 980 KB Output is correct
8 Correct 373 ms 1124 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 1124 KB Output is correct
2 Correct 421 ms 1124 KB Output is correct
3 Correct 428 ms 1124 KB Output is correct
4 Correct 402 ms 1124 KB Output is correct
5 Correct 373 ms 1124 KB Output is correct
6 Correct 289 ms 1172 KB Output is correct
7 Correct 352 ms 1172 KB Output is correct
8 Correct 353 ms 1228 KB Output is correct
9 Correct 401 ms 1276 KB Output is correct
10 Correct 370 ms 1276 KB Output is correct
11 Correct 366 ms 1448 KB Output is correct
12 Correct 433 ms 1448 KB Output is correct
13 Correct 447 ms 1448 KB Output is correct
14 Correct 384 ms 1448 KB Output is correct
15 Correct 404 ms 1528 KB Output is correct
16 Correct 380 ms 1548 KB Output is correct
17 Correct 470 ms 1600 KB Output is correct
18 Correct 391 ms 1600 KB Output is correct
19 Correct 381 ms 1600 KB Output is correct
20 Correct 389 ms 1600 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 129 ms 1680 KB Wrong Answer[2]
2 Halted 0 ms 0 KB -