oj.uz

Submission #54757

# Submission time Handle Problem Language Result Execution time Memory
54757 2018-07-05T02:27:41 Z ksun48 Park (JOI17_park) C++14
77 / 100
 1265 ms 1200 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(4844444);
	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 248 KB Output is correct
2 Correct 10 ms 484 KB Output is correct
3 Correct 9 ms 484 KB Output is correct
4 Correct 11 ms 588 KB Output is correct
5 Correct 9 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 816 KB Output is correct
2 Correct 184 ms 816 KB Output is correct
3 Correct 181 ms 816 KB Output is correct
4 Correct 298 ms 872 KB Output is correct
5 Correct 268 ms 872 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 872 KB Output is correct
2 Correct 271 ms 872 KB Output is correct
3 Correct 291 ms 876 KB Output is correct
4 Correct 337 ms 876 KB Output is correct
5 Correct 354 ms 876 KB Output is correct
6 Correct 272 ms 1032 KB Output is correct
7 Correct 318 ms 1032 KB Output is correct
8 Correct 269 ms 1032 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 1032 KB Output is correct
2 Correct 267 ms 1032 KB Output is correct
3 Correct 259 ms 1032 KB Output is correct
4 Correct 277 ms 1032 KB Output is correct
5 Correct 315 ms 1032 KB Output is correct
6 Correct 240 ms 1032 KB Output is correct
7 Correct 293 ms 1076 KB Output is correct
8 Correct 297 ms 1076 KB Output is correct
9 Correct 312 ms 1076 KB Output is correct
10 Correct 253 ms 1076 KB Output is correct
11 Correct 254 ms 1076 KB Output is correct
12 Correct 287 ms 1076 KB Output is correct
13 Correct 278 ms 1076 KB Output is correct
14 Correct 257 ms 1076 KB Output is correct
15 Correct 277 ms 1076 KB Output is correct
16 Correct 354 ms 1076 KB Output is correct
17 Correct 312 ms 1096 KB Output is correct
18 Correct 276 ms 1196 KB Output is correct
19 Correct 268 ms 1200 KB Output is correct
20 Correct 249 ms 1200 KB Output is correct

Subtask #5
0 / 23.0

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