oj.uz

Submission #826558

# Submission time Handle Problem Language Result Execution time Memory
826558 2023-08-15T16:52:07 Z MohamedAhmed04 Park (JOI17_park) C++14
67 / 100
 279 ms 588 KB 
#include <bits/stdc++.h>
#include "park.h"

using namespace std ;

const int MAX = 1400 + 10 ;

static int Place[MAX] ;

int n ;
int deg[MAX] ;
vector< vector<int> >adj(MAX) ;
int mark[MAX] ;

vector<int>order ;

void dfs(int node)
{
	order.push_back(node) ;
	for(auto &child : adj[node])
		dfs(child) ;
}

bool check(int mid , int node)
{
	for(int i = 0 ; i < n ; ++i)
	{
		if(!mark[i])
			Place[i] = 1 ;
		else
			Place[i] = 0 ;
	}
	for(int i = 0 ; i <= mid ; ++i)
		Place[order[i]] = 1 ;
	return Ask(0 , node , Place) ;
}

int Find_Par(int node)
{
	int l = 0 , r = (int)(order.size()) - 1 ;
	int node2 = 0 ;
	while(l <= r)
	{
		int mid = (l + r) >> 1 ;
		if(check(mid , node))
			node2 = order[mid] , r = mid-1 ;
		else
			l = mid+1 ;
	}
	return node2 ;
}

bool check2(vector<int>&v , int l , int r , int node)
{
	for(int i = 0 ; i < n ; ++i)
		Place[i] = 1 ;
	for(int i = l ; i <= r ; ++i)
		Place[v[i]] = 0 ;
	return (!Ask(0 , node , Place)) ;
}

bool cmp(int a , int b)
{
	for(int i = 0 ; i < n ; ++i)
		Place[i] = 1 ;
	Place[a] = 0 ;
	return (!Ask(0 , b , Place)) ; //if false then a is ancestor b
}

vector<int>Find_Ancestors(int node)
{
	vector<int>v ;
	for(int i = 0 ; i < n ; ++i)
	{
		if((!mark[i]) && i != node)
			v.push_back(i) ;
	}
	int prv = -1 ;
	vector<int>ancestors ; 
	for(int i = 0 ; i < v.size() ; ++i)
	{
		int l = prv+1 , r = (int)(v.size()) - 1 ;
		int idx = -1 ;
		while(l <= r)
		{
			int mid = (l + r) >> 1 ;
			if(check2(v , prv+1 , mid , node))
				idx = mid , r = mid-1 ;
			else
				l = mid+1 ;
		}
		if(idx == -1)
			break ;
		ancestors.push_back(v[idx]) ;
		prv = idx ;
	}
	sort(ancestors.begin() , ancestors.end() , cmp) ;
	return ancestors ;
}

void solve(int node)
{
	order.clear() ;
	dfs(0) ;
	int par = Find_Par(node) ;
	vector<int>v = Find_Ancestors(node) ;
	if(v.size())
	{
		adj[par].push_back(v[0]) ;
		for(int i = 0 ; i+1 < v.size() ; ++i)
			adj[v[i]].push_back(v[i+1]) ;
		adj[v.back()].push_back(node) ;
		for(auto &x : v)
			mark[x] = 1 ;
	}
	else
		adj[par].push_back(node) ;
	mark[node] = 1 ;
}

void Detect(int T, int N) 
{
	n = N ;
	mark[0] = 1 ;
	for(int i = 1 ; i < n ; ++i)
	{
		if(mark[i])
			continue ;
		solve(i) ;
	}
	for(int i = 0 ; i < n ; ++i)
	{
		for(auto &child : adj[i])
			Answer(min(i , child) , max(i , child)) ;
	}
	return ;
}

Compilation message

park.cpp: In function 'std::vector<int> Find_Ancestors(int)':
park.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0 ; i < v.size() ; ++i)
      |                  ~~^~~~~~~~~~
park.cpp: In function 'void solve(int)':
park.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for(int i = 0 ; i+1 < v.size() ; ++i)
      |                   ~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 480 KB Output is correct
2 Correct 163 ms 520 KB Output is correct
3 Correct 166 ms 520 KB Output is correct
4 Correct 164 ms 504 KB Output is correct
5 Correct 164 ms 420 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 436 KB Output is correct
2 Correct 198 ms 468 KB Output is correct
3 Correct 210 ms 460 KB Output is correct
4 Correct 193 ms 456 KB Output is correct
5 Correct 238 ms 464 KB Output is correct
6 Correct 190 ms 472 KB Output is correct
7 Correct 188 ms 468 KB Output is correct
8 Correct 200 ms 456 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 424 KB Output is correct
2 Correct 212 ms 468 KB Output is correct
3 Correct 220 ms 468 KB Output is correct
4 Correct 190 ms 480 KB Output is correct
5 Correct 209 ms 496 KB Output is correct
6 Correct 197 ms 496 KB Output is correct
7 Correct 196 ms 468 KB Output is correct
8 Correct 213 ms 468 KB Output is correct
9 Correct 198 ms 452 KB Output is correct
10 Correct 192 ms 476 KB Output is correct
11 Correct 188 ms 488 KB Output is correct
12 Correct 212 ms 476 KB Output is correct
13 Correct 224 ms 492 KB Output is correct
14 Correct 187 ms 476 KB Output is correct
15 Correct 207 ms 480 KB Output is correct
16 Correct 200 ms 588 KB Output is correct
17 Correct 147 ms 548 KB Output is correct
18 Correct 188 ms 492 KB Output is correct
19 Correct 206 ms 508 KB Output is correct
20 Correct 211 ms 472 KB Output is correct

Subtask #5
0 / 23.0

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