oj.uz

답안 #54768

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54768 2018-07-05T04:45:05 Z ksun48 Park (JOI17_park) C++14
77 / 100
 1459 ms 1020 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(48488);
	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 376 KB Output is correct
2 Correct 9 ms 488 KB Output is correct
3 Correct 10 ms 616 KB Output is correct
4 Correct 10 ms 616 KB Output is correct
5 Correct 8 ms 616 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 680 KB Output is correct
2 Correct 218 ms 780 KB Output is correct
3 Correct 183 ms 896 KB Output is correct
4 Correct 279 ms 896 KB Output is correct
5 Correct 279 ms 896 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 896 KB Output is correct
2 Correct 308 ms 896 KB Output is correct
3 Correct 346 ms 896 KB Output is correct
4 Correct 284 ms 896 KB Output is correct
5 Correct 345 ms 952 KB Output is correct
6 Correct 295 ms 952 KB Output is correct
7 Correct 310 ms 952 KB Output is correct
8 Correct 271 ms 952 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 952 KB Output is correct
2 Correct 250 ms 952 KB Output is correct
3 Correct 243 ms 952 KB Output is correct
4 Correct 277 ms 952 KB Output is correct
5 Correct 239 ms 952 KB Output is correct
6 Correct 226 ms 952 KB Output is correct
7 Correct 262 ms 1020 KB Output is correct
8 Correct 301 ms 1020 KB Output is correct
9 Correct 291 ms 1020 KB Output is correct
10 Correct 250 ms 1020 KB Output is correct
11 Correct 283 ms 1020 KB Output is correct
12 Correct 270 ms 1020 KB Output is correct
13 Correct 292 ms 1020 KB Output is correct
14 Correct 304 ms 1020 KB Output is correct
15 Correct 300 ms 1020 KB Output is correct
16 Correct 310 ms 1020 KB Output is correct
17 Correct 284 ms 1020 KB Output is correct
18 Correct 290 ms 1020 KB Output is correct
19 Correct 268 ms 1020 KB Output is correct
20 Correct 254 ms 1020 KB Output is correct

Subtask #5
0 / 23.0

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