oj.uz

Submission #412731

# Submission time Handle Problem Language Result Execution time Memory
412731 2021-05-27T11:53:42 Z amoo_safar Park (JOI17_park) C++17
67 / 100
 690 ms 868 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[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;
	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 685 ms 572 KB Output is correct
2 Correct 280 ms 632 KB Output is correct
3 Correct 332 ms 620 KB Output is correct
4 Correct 676 ms 748 KB Output is correct
5 Correct 690 ms 664 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 596 KB Output is correct
2 Correct 427 ms 552 KB Output is correct
3 Correct 444 ms 688 KB Output is correct
4 Correct 440 ms 552 KB Output is correct
5 Correct 484 ms 692 KB Output is correct
6 Correct 434 ms 724 KB Output is correct
7 Correct 427 ms 572 KB Output is correct
8 Correct 433 ms 596 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 532 KB Output is correct
2 Correct 491 ms 688 KB Output is correct
3 Correct 488 ms 596 KB Output is correct
4 Correct 517 ms 688 KB Output is correct
5 Correct 537 ms 692 KB Output is correct
6 Correct 567 ms 588 KB Output is correct
7 Correct 570 ms 580 KB Output is correct
8 Correct 509 ms 556 KB Output is correct
9 Correct 490 ms 580 KB Output is correct
10 Correct 570 ms 640 KB Output is correct
11 Correct 549 ms 868 KB Output is correct
12 Correct 482 ms 560 KB Output is correct
13 Correct 597 ms 600 KB Output is correct
14 Correct 545 ms 720 KB Output is correct
15 Correct 587 ms 564 KB Output is correct
16 Correct 432 ms 556 KB Output is correct
17 Correct 682 ms 764 KB Output is correct
18 Correct 521 ms 704 KB Output is correct
19 Correct 624 ms 628 KB Output is correct
20 Correct 515 ms 572 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 628 KB Output is correct
2 Correct 548 ms 640 KB Output is correct
3 Correct 479 ms 752 KB Output is correct
4 Incorrect 541 ms 744 KB Wrong Answer[6]
5 Halted 0 ms 0 KB -