oj.uz

답안 #54752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54752 2018-07-05T02:24:08 Z ksun48 Park (JOI17_park) C++14
20 / 100
 1287 ms 1320 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 < 9; q++){
			int b = v[rand() % v.size()];
			int c = v[rand() % v.size()];
			if(check_subtree(b, a, c, n)){
				numdiff++;
			}
		}
		if(numdiff >= 4){
			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(48);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 10 ms 460 KB Output is correct
3 Correct 8 ms 460 KB Output is correct
4 Correct 8 ms 484 KB Output is correct
5 Correct 14 ms 484 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 349 ms 700 KB Output is correct
2 Correct 220 ms 728 KB Output is correct
3 Correct 203 ms 728 KB Output is correct
4 Correct 299 ms 728 KB Output is correct
5 Correct 327 ms 768 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 768 KB Output is correct
2 Correct 300 ms 768 KB Output is correct
3 Incorrect 399 ms 768 KB Wrong Answer[5]
4 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 768 KB Output is correct
2 Correct 314 ms 768 KB Output is correct
3 Correct 303 ms 768 KB Output is correct
4 Correct 355 ms 784 KB Output is correct
5 Correct 299 ms 800 KB Output is correct
6 Correct 266 ms 896 KB Output is correct
7 Correct 308 ms 1076 KB Output is correct
8 Correct 329 ms 1088 KB Output is correct
9 Correct 297 ms 1124 KB Output is correct
10 Correct 347 ms 1124 KB Output is correct
11 Correct 290 ms 1124 KB Output is correct
12 Correct 359 ms 1124 KB Output is correct
13 Correct 288 ms 1264 KB Output is correct
14 Correct 320 ms 1264 KB Output is correct
15 Correct 333 ms 1264 KB Output is correct
16 Correct 322 ms 1264 KB Output is correct
17 Correct 280 ms 1264 KB Output is correct
18 Correct 375 ms 1264 KB Output is correct
19 Correct 295 ms 1264 KB Output is correct
20 Incorrect 378 ms 1320 KB Wrong Answer[5]

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1287 ms 1320 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -