oj.uz

Submission #54759

# Submission time Handle Problem Language Result Execution time Memory
54759 2018-07-05T02:30:04 Z ksun48 Park (JOI17_park) C++14
77 / 100
 1196 ms 1004 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 < 3; 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 376 KB Output is correct
2 Correct 9 ms 488 KB Output is correct
3 Correct 8 ms 488 KB Output is correct
4 Correct 9 ms 488 KB Output is correct
5 Correct 8 ms 540 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 668 KB Output is correct
2 Correct 202 ms 696 KB Output is correct
3 Correct 187 ms 700 KB Output is correct
4 Correct 248 ms 796 KB Output is correct
5 Correct 251 ms 796 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 820 KB Output is correct
2 Correct 266 ms 820 KB Output is correct
3 Correct 275 ms 828 KB Output is correct
4 Correct 234 ms 828 KB Output is correct
5 Correct 416 ms 828 KB Output is correct
6 Correct 305 ms 828 KB Output is correct
7 Correct 225 ms 828 KB Output is correct
8 Correct 230 ms 828 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 828 KB Output is correct
2 Correct 239 ms 828 KB Output is correct
3 Correct 238 ms 828 KB Output is correct
4 Correct 268 ms 876 KB Output is correct
5 Correct 228 ms 876 KB Output is correct
6 Correct 226 ms 876 KB Output is correct
7 Correct 249 ms 1004 KB Output is correct
8 Correct 238 ms 1004 KB Output is correct
9 Correct 254 ms 1004 KB Output is correct
10 Correct 250 ms 1004 KB Output is correct
11 Correct 210 ms 1004 KB Output is correct
12 Correct 277 ms 1004 KB Output is correct
13 Correct 288 ms 1004 KB Output is correct
14 Correct 244 ms 1004 KB Output is correct
15 Correct 257 ms 1004 KB Output is correct
16 Correct 293 ms 1004 KB Output is correct
17 Correct 252 ms 1004 KB Output is correct
18 Correct 229 ms 1004 KB Output is correct
19 Correct 258 ms 1004 KB Output is correct
20 Correct 219 ms 1004 KB Output is correct

Subtask #5
0 / 23.0

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