oj.uz

Submission #412728

# Submission time Handle Problem Language Result Execution time Memory
412728 2021-05-27T11:48:24 Z amoo_safar Park (JOI17_park) C++17
67 / 100
 746 ms 800 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);
	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]);
	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[V[i]] = (i < mid);
		if(Query(V[0], u))
			R = mid;
		else
			L = mid;
	}
	Add_Edge(u, V[L]);

	for(auto x : V)
		mk[x] = 0;
	mk[V[L]] = 1;
	for(auto x : V){
		if(mk[x]) continue;
		dfs.clear();
		DFS(x);
		vector<int> com = dfs;
		Find_Edges(com, 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 628 KB Output is correct
2 Correct 286 ms 760 KB Output is correct
3 Correct 398 ms 592 KB Output is correct
4 Correct 728 ms 800 KB Output is correct
5 Correct 730 ms 800 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 720 KB Output is correct
2 Correct 508 ms 576 KB Output is correct
3 Correct 521 ms 712 KB Output is correct
4 Correct 477 ms 628 KB Output is correct
5 Correct 580 ms 696 KB Output is correct
6 Correct 519 ms 624 KB Output is correct
7 Correct 497 ms 616 KB Output is correct
8 Correct 512 ms 616 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 536 KB Output is correct
2 Correct 561 ms 616 KB Output is correct
3 Correct 576 ms 620 KB Output is correct
4 Correct 616 ms 624 KB Output is correct
5 Correct 600 ms 588 KB Output is correct
6 Correct 579 ms 660 KB Output is correct
7 Correct 644 ms 728 KB Output is correct
8 Correct 569 ms 592 KB Output is correct
9 Correct 593 ms 592 KB Output is correct
10 Correct 593 ms 652 KB Output is correct
11 Correct 585 ms 720 KB Output is correct
12 Correct 552 ms 576 KB Output is correct
13 Correct 666 ms 588 KB Output is correct
14 Correct 605 ms 588 KB Output is correct
15 Correct 680 ms 628 KB Output is correct
16 Correct 562 ms 584 KB Output is correct
17 Correct 710 ms 800 KB Output is correct
18 Correct 589 ms 668 KB Output is correct
19 Correct 691 ms 756 KB Output is correct
20 Correct 612 ms 584 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 651 ms 624 KB Output is correct
2 Incorrect 622 ms 712 KB Wrong Answer[6]
3 Halted 0 ms 0 KB -