oj.uz

Submission #54771

# Submission time Handle Problem Language Result Execution time Memory
54771 2018-07-05T04:47:04 Z ksun48 Park (JOI17_park) C++14
47 / 100
 1325 ms 1048 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(3338);
	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 8 ms 356 KB Output is correct
3 Correct 8 ms 432 KB Output is correct
4 Correct 8 ms 508 KB Output is correct
5 Correct 8 ms 508 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 768 KB Output is correct
2 Correct 188 ms 768 KB Output is correct
3 Correct 182 ms 840 KB Output is correct
4 Correct 275 ms 840 KB Output is correct
5 Correct 278 ms 852 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 852 KB Output is correct
2 Correct 295 ms 852 KB Output is correct
3 Correct 356 ms 852 KB Output is correct
4 Correct 292 ms 852 KB Output is correct
5 Correct 377 ms 852 KB Output is correct
6 Correct 266 ms 852 KB Output is correct
7 Correct 275 ms 880 KB Output is correct
8 Correct 263 ms 928 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 928 KB Output is correct
2 Correct 263 ms 928 KB Output is correct
3 Correct 231 ms 928 KB Output is correct
4 Correct 315 ms 944 KB Output is correct
5 Correct 348 ms 1020 KB Output is correct
6 Correct 220 ms 1020 KB Output is correct
7 Correct 294 ms 1020 KB Output is correct
8 Correct 312 ms 1020 KB Output is correct
9 Correct 241 ms 1020 KB Output is correct
10 Correct 251 ms 1020 KB Output is correct
11 Correct 225 ms 1020 KB Output is correct
12 Correct 272 ms 1020 KB Output is correct
13 Correct 286 ms 1020 KB Output is correct
14 Correct 270 ms 1024 KB Output is correct
15 Incorrect 346 ms 1048 KB Wrong Answer[5]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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