Submission #826558

#	Time	Username	Problem	Language	Result	Execution time	Memory
826558		MohamedAhmed04	Park (JOI17_park)	C++14	67 / 100	279 ms	588 KiB

park

#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 (stderr)

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
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23