oj.uz

Submission #521764

# Submission time Handle Problem Language Result Execution time Memory
521764 2022-02-03T02:28:23 Z ainta Park (JOI17_park) C++17
100 / 100
 554 ms 616 KB 
#include "park.h"
#include <cstdio>
#include <vector>
using namespace std;
#define si(x) (int)(x.size())

static int Place[1400], n, fin[1400], chk[1400], U[1400], vi[1400];
static vector<int>E[1400], TP, PP;
void Tra(int a){
	vi[a]=1;
	TP.push_back(a);
	for(auto &t: E[a]){
		if(U[t] || vi[t])continue;
		Tra(t);
	}
}
void Go(int rt, int a, int cer){
	for(int i=0;i<n;i++)vi[i]=0;
	TP.clear();
	Tra(rt);
	int m = si(TP);
	if(!cer){
		for(int i=0;i<n;i++)Place[i]=0;
		for(int i=0;i<m;i++)Place[TP[i]]=1;
		Place[a] = 1;
		if(!Ask(min(rt,a),max(rt,a),Place))return;
	}
	int b = 1, e = m-1, r = m;
	while(b<=e){
		int mid = (b+e)>>1;
		for(int i=0;i<n;i++)Place[i]=0;
		for(int i=0;i<mid;i++)Place[TP[i]]=1;
		Place[a]=1;
		if(Ask(min(rt,a),max(rt,a),Place)){
			r = mid;
			e = mid-1;
		}
		else b = mid+1;
	}
	int x = TP[r-1];
	PP.push_back(x);
	U[x] = 1;
	for(auto &y : E[x]){
		if(!U[y]){
			Go(y, a, 0);
		}
	}
}
void Add(int a){
	int i;
	PP.clear();
	for(i=0;i<n;i++)U[i]=0;
	Go(0, a, 1);
	fin[a] = 1;
	for(auto &t: PP){
		Answer(min(a, t),max(a,t));
		E[a].push_back(t);
		E[t].push_back(a);
	}
}
void DFS(int a){
	chk[a] = 1;
	int c = 0;
	for(int i=0;i<n;i++){
		if(chk[i]||fin[i])continue;
		c++;
	}
	int b = 0, e = c, mid, r = -1;
	while(b<=e){
		mid = (b+e)>>1;
		for(int i=0;i<n;i++){
			Place[i] = fin[i];
		}
		int t=0;
		for(int i=0;i<n;i++){
			if(chk[i]||fin[i])continue;
			if(t<mid){
				Place[i] = 1;
			}
			t++;
		}
		Place[a] = 1;
		if(Ask(0, a, Place)){
			r = mid;
			e = mid-1;
		}
		else b = mid+1;
	}
	if(r == 0){
		Add(a);
		return;
	}
	else{
		int t=0, x = -1;
		for(int i=0;i<n;i++){
			if(chk[i]||fin[i])continue;
			t++;
			if(t==r)x = i;
		}
		DFS(x);
		DFS(a);
	}
}
void Detect(int T, int N) {
	n = N;
	int i;
	fin[0]=1;
	for(i=1;i<N;i++){
		if(fin[i])continue;
		DFS(i);
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 324 KB Output is correct
2 Correct 12 ms 496 KB Output is correct
3 Correct 9 ms 320 KB Output is correct
4 Correct 26 ms 332 KB Output is correct
5 Correct 68 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 552 KB Output is correct
2 Correct 198 ms 488 KB Output is correct
3 Correct 233 ms 476 KB Output is correct
4 Correct 546 ms 616 KB Output is correct
5 Correct 540 ms 532 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 444 KB Output is correct
2 Correct 340 ms 428 KB Output is correct
3 Correct 361 ms 452 KB Output is correct
4 Correct 324 ms 436 KB Output is correct
5 Correct 383 ms 564 KB Output is correct
6 Correct 348 ms 444 KB Output is correct
7 Correct 347 ms 440 KB Output is correct
8 Correct 349 ms 436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 444 KB Output is correct
2 Correct 413 ms 448 KB Output is correct
3 Correct 403 ms 452 KB Output is correct
4 Correct 423 ms 460 KB Output is correct
5 Correct 436 ms 456 KB Output is correct
6 Correct 456 ms 484 KB Output is correct
7 Correct 444 ms 532 KB Output is correct
8 Correct 400 ms 452 KB Output is correct
9 Correct 394 ms 484 KB Output is correct
10 Correct 447 ms 452 KB Output is correct
11 Correct 448 ms 580 KB Output is correct
12 Correct 385 ms 496 KB Output is correct
13 Correct 495 ms 580 KB Output is correct
14 Correct 430 ms 500 KB Output is correct
15 Correct 494 ms 452 KB Output is correct
16 Correct 351 ms 452 KB Output is correct
17 Correct 542 ms 588 KB Output is correct
18 Correct 425 ms 584 KB Output is correct
19 Correct 504 ms 460 KB Output is correct
20 Correct 434 ms 452 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 488 KB Output is correct
2 Correct 453 ms 452 KB Output is correct
3 Correct 391 ms 492 KB Output is correct
4 Correct 448 ms 492 KB Output is correct
5 Correct 458 ms 572 KB Output is correct
6 Correct 514 ms 544 KB Output is correct
7 Correct 476 ms 576 KB Output is correct
8 Correct 479 ms 524 KB Output is correct
9 Correct 458 ms 512 KB Output is correct
10 Correct 410 ms 580 KB Output is correct
11 Correct 413 ms 460 KB Output is correct
12 Correct 451 ms 496 KB Output is correct
13 Correct 422 ms 440 KB Output is correct
14 Correct 468 ms 468 KB Output is correct
15 Correct 439 ms 460 KB Output is correct
16 Correct 364 ms 560 KB Output is correct
17 Correct 554 ms 508 KB Output is correct
18 Correct 431 ms 516 KB Output is correct