oj.uz

Submission #60407

# Submission time Handle Problem Language Result Execution time Memory
60407 2018-07-24T06:38:20 Z 김세빈(#1743) Park (JOI17_park) C++11
10 / 100
 300 ms 856 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[k] = 1;
	}
	P[0] = 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 + 1 == 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 'bool check_dep(int, int)':
park.cpp:30:11: warning: unused variable 't' [-Wunused-variable]
   for(int t: K[i]) P[k] = 1;
           ^
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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 740 KB Output is correct
2 Correct 61 ms 740 KB Output is correct
3 Correct 113 ms 740 KB Output is correct
4 Correct 283 ms 812 KB Output is correct
5 Correct 258 ms 856 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 23.0

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