oj.uz

Submission #54767

# Submission time Handle Problem Language Result Execution time Memory
54767 2018-07-05T04:44:04 Z ksun48 Park (JOI17_park) C++14
47 / 100
 1343 ms 1012 KB 
#include <bits/stdc++.h>
#include "park.h"
using namespace std;

int P[1400];
int ask(int a, int b){
	if(P[a] == 0 || P[b] == 0) return 0;
	if(a == b) return 1;
	return Ask(min(a,b), max(a,b), P);
}

void found(int a, int b){
	Answer(min(a,b), max(a,b));
}

void solve1(int n){
	for(int i = 0; i < n; i++){
		P[i] = 0;
	}
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			P[i] = P[j] = 1;
			if(ask(i,j)){
				found(i,j);
			}
			P[i] = P[j] = 0;
		}
	}
}

int check_edge(int a, int b, int n){
	if(a == b) return 0;
	for(int i = 0; i < n; i++){
		P[i] = 0;
	}
	P[a] = P[b] = 1;
	return ask(a, b);
}

int check_subtree(int a, int b, int c, int n){
	// a-b is an edge, check if x == b or x is in b's side
	for(int i = 0; i < n; i++){
		P[i] = 1;
	}
	P[b] = 0;
	if(ask(a,c)){
		return 0;
	}
	return 1;
}

void solvetreev(vector<int> v, int n){
	if(v.size() <= 1) return;
	int a;
	while(1){
		a = v[rand() % v.size()];
		int numdiff = 0;

		// 9 trials
		for(int q = 0; q < 2; q++){
			int b = v[rand() % v.size()];
			int c = v[rand() % v.size()];
			if(check_subtree(b, a, c, n)){
				numdiff++;
			}
		}
		if(numdiff >= 2){
			break;
		}
	}
	vector<pair<int, vector<int> > > children;
	for(int x : v){
		if(check_edge(a, x, n)){
			found(a,x);
			children.push_back({x, vector<int>()});
		}
	}
	for(int x : v){
		if(x == a) continue;
		while(1){
			int did = 0;
			for(int i = 0; i + 1 < children.size(); i++){
				if(children[i+1].second.size() > children[i].second.size()){
					swap(children[i], children[i+1]);
					did = 1;
				}
			}
			if(!did) break;
		}
		for(int i = 0; i < children.size(); i++){
			if(check_subtree(a, children[i].first, x, n)){
				children[i].second.push_back(x);
				break;
			}
		}
	}
	for(int i = 0; i < children.size(); i++){
		solvetreev(children[i].second, n);
	}
	return;
}

void solve2(int n){
	vector<int> v;
	for(int i = 0; i < n; i++){
		v.push_back(i);
	}
	solvetreev(v, n);
}
void Detect(int T, int N) {
	srand(4848);
	if(T == 1){
		solve1(N);
	} else if(T >= 2){
		solve2(N);
	}
}

Compilation message

park.cpp: In function 'void solvetreev(std::vector<int>, int)':
park.cpp:82:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i + 1 < children.size(); i++){
                   ~~~~~~^~~~~~~~~~~~~~~~~
park.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < children.size(); i++){
                  ~~^~~~~~~~~~~~~~~~~
park.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < children.size(); i++){
                 ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 13 ms 452 KB Output is correct
3 Correct 8 ms 452 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 9 ms 564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 672 KB Output is correct
2 Correct 179 ms 744 KB Output is correct
3 Correct 190 ms 744 KB Output is correct
4 Correct 278 ms 844 KB Output is correct
5 Correct 334 ms 844 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 844 KB Output is correct
2 Correct 285 ms 852 KB Output is correct
3 Correct 255 ms 868 KB Output is correct
4 Correct 302 ms 868 KB Output is correct
5 Correct 297 ms 868 KB Output is correct
6 Correct 372 ms 880 KB Output is correct
7 Correct 306 ms 880 KB Output is correct
8 Correct 232 ms 880 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 880 KB Output is correct
2 Correct 239 ms 880 KB Output is correct
3 Correct 246 ms 880 KB Output is correct
4 Correct 274 ms 880 KB Output is correct
5 Correct 282 ms 888 KB Output is correct
6 Correct 224 ms 888 KB Output is correct
7 Correct 261 ms 888 KB Output is correct
8 Correct 316 ms 888 KB Output is correct
9 Correct 327 ms 892 KB Output is correct
10 Correct 266 ms 892 KB Output is correct
11 Correct 283 ms 892 KB Output is correct
12 Correct 336 ms 896 KB Output is correct
13 Correct 374 ms 1012 KB Output is correct
14 Correct 275 ms 1012 KB Output is correct
15 Correct 377 ms 1012 KB Output is correct
16 Correct 253 ms 1012 KB Output is correct
17 Correct 280 ms 1012 KB Output is correct
18 Correct 257 ms 1012 KB Output is correct
19 Correct 361 ms 1012 KB Output is correct
20 Incorrect 309 ms 1012 KB Wrong Answer[5]

Subtask #5
0 / 23.0

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