| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 826557 | MohamedAhmed04 | Park (JOI17_park) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "grader.cpp"
#include <bits/stdc++.h>
#include "park.h"
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
int rand(int l , int r)
{
return uniform_int_distribution<int>(l , r)(rng) ;
}
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 ;
}