oj.uz

Submission #412734

# Submission time Handle Problem Language Result Execution time Memory
412734 2021-05-27T12:02:13 Z amoo_safar Park (JOI17_park) C++17
100 / 100
 688 ms 972 KB 
#include "park.h"
#include<bits/stdc++.h>
#define pb push_back

using namespace std;

static int Place[1400];

const int N = 1405;

int Query(int u, int v){
	if(u > v) swap(u, v);
	return Ask(u, v, Place);
}
int n;
int added[N];
vector<int> ord, rem;

void Add(int u){
	if(added[u])
		return;

	rem = {u};
	for(int i = 0; i < n; i++)
		if(!added[i] && i != u)
			rem.pb(i);
	int L = 0, R = rem.size();
	while(L + 1 < R){
		int mid = (L + R) >> 1;
		
		memset(Place, 0, sizeof Place);
		for(auto x : ord)
			Place[x] = 1;
		
		for(int i = 0; i < mid; i++)
			Place[rem[i]] = 1;
		
		if(Query(ord[0], rem[0])) R = mid;
		else L = mid;
	}
	if(R == 1){
		added[u] = 1;
		ord.pb(u);
		return ;
	}
	int v = rem[L];
	Add(v);
	Add(u);
}

vector<int> G[N];
void Add_Edge(int u, int v){
	if(u > v) swap(u, v);
	Answer(u, v);
	// cerr << "!! " << u << ' ' << v << '\n';
	G[u].pb(v);
	G[v].pb(u);
}

vector<int> dfs;
int mk[N];
void DFS(int u){
	mk[u] = 1;
	dfs.pb(u);
	for(auto adj : G[u])
		if(!mk[adj])
			DFS(adj);
}
void Find_Edges(vector<int> V, int u){
	if(V.empty())
		return ;
	memset(Place, 0, sizeof Place);
	for(auto x : V)
		Place[x] = 1;
	Place[u] = 1;
	if(!Query(V[0], u)) return ;
	memset(mk, 1, sizeof mk);
	for(auto x : V)
		mk[x] = 0;
	dfs.clear();
	DFS(V[0]);
	
	assert(dfs.size() == V.size());

	int L = 0, R = V.size();
	while(L + 1 < R){
		int mid = (L + R) >> 1;
		for(int i = 0; i < (int) V.size(); i++)
			Place[dfs[i]] = (i < mid);
		if(Query(dfs[0], u))
			R = mid;
		else
			L = mid;
	}
	Add_Edge(u, dfs[L]);

	for(auto x : V)
		mk[x] = 0;
	mk[dfs[L]] = 1;
	vector< vector<int> > com;
	for(auto x : V){
		if(mk[x]) continue;
		dfs.clear();
		DFS(x);
		com.pb(dfs);
	}
	for(auto cm : com)
		Find_Edges(cm, u);
}

void Detect(int T, int _n) {
	assert(T < 6);
	n = _n;
	ord.pb(0); added[0] = 1;
	for(int i = 1; i < n; i++)
		Add(i);
	vector<int> nw = {0};
	for(int i = 1; i < n; i++){
		Find_Edges(nw, ord[i]);
		nw.pb(ord[i]);
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 14 ms 556 KB Output is correct
3 Correct 12 ms 460 KB Output is correct
4 Correct 26 ms 580 KB Output is correct
5 Correct 53 ms 572 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 872 KB Output is correct
2 Correct 264 ms 580 KB Output is correct
3 Correct 331 ms 724 KB Output is correct
4 Correct 672 ms 836 KB Output is correct
5 Correct 668 ms 760 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 552 KB Output is correct
2 Correct 423 ms 560 KB Output is correct
3 Correct 455 ms 612 KB Output is correct
4 Correct 417 ms 580 KB Output is correct
5 Correct 467 ms 552 KB Output is correct
6 Correct 431 ms 680 KB Output is correct
7 Correct 423 ms 548 KB Output is correct
8 Correct 435 ms 696 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 560 KB Output is correct
2 Correct 485 ms 616 KB Output is correct
3 Correct 487 ms 556 KB Output is correct
4 Correct 517 ms 680 KB Output is correct
5 Correct 540 ms 744 KB Output is correct
6 Correct 546 ms 584 KB Output is correct
7 Correct 553 ms 736 KB Output is correct
8 Correct 497 ms 552 KB Output is correct
9 Correct 491 ms 548 KB Output is correct
10 Correct 549 ms 568 KB Output is correct
11 Correct 540 ms 836 KB Output is correct
12 Correct 479 ms 580 KB Output is correct
13 Correct 580 ms 708 KB Output is correct
14 Correct 506 ms 580 KB Output is correct
15 Correct 599 ms 636 KB Output is correct
16 Correct 440 ms 712 KB Output is correct
17 Correct 672 ms 804 KB Output is correct
18 Correct 516 ms 564 KB Output is correct
19 Correct 638 ms 580 KB Output is correct
20 Correct 515 ms 564 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 708 KB Output is correct
2 Correct 534 ms 676 KB Output is correct
3 Correct 472 ms 560 KB Output is correct
4 Correct 540 ms 584 KB Output is correct
5 Correct 533 ms 636 KB Output is correct
6 Correct 633 ms 732 KB Output is correct
7 Correct 555 ms 720 KB Output is correct
8 Correct 584 ms 780 KB Output is correct
9 Correct 572 ms 600 KB Output is correct
10 Correct 493 ms 600 KB Output is correct
11 Correct 525 ms 972 KB Output is correct
12 Correct 549 ms 764 KB Output is correct
13 Correct 519 ms 656 KB Output is correct
14 Correct 554 ms 836 KB Output is correct
15 Correct 522 ms 708 KB Output is correct
16 Correct 430 ms 580 KB Output is correct
17 Correct 688 ms 924 KB Output is correct
18 Correct 512 ms 596 KB Output is correct