| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 594599 | Koosha_mv | 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 "park.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=1505;
mt19937 rng(time(nullptr));
int n,vis[N],mark[N],place[N];
vector<int> g[N];
void reset(){
f(i,0,n) place[i]=0;
}
int rand(int l,int r){
uniform_int_distribution<int> rnd(l,r-1);
return rnd(rng);
}
int ask(int s,int t){
if(s>t) swap(s,t);
int res=Ask(s,t,place);
return res;
}
void path(int s,int t,vector<int> vec){
if(vec.size()==0){
if(s>t) swap(s,t);
//cout<<s<<" -> "<<t<<endl;
Answer(s,t);
g[s].pb(t);
g[t].pb(s);
return ;
}
int id=vec[rand(0,vec.size())];
reset();
place[s]=place[t]=1;
for(auto x : vec){
place[x]=1;
}
vector<int> L,R;
for(auto x : vec){
if(x==id) continue ;
place[x]=0;
if(ask(s,id)==0) L.pb(x);
else R.pb(x);
place[x]=1;
}
path(s,id,L);
path(id,t,R);
}
void dfs1(int u,int p,vector<int> &vec){
par[u]=p;
vec.pb(u);
for(auto v : g[u]){
if(v==p || vis[v]) continue ;
dfs1(v,u,vec);
}
}
void solve(int x,int u){
vector<int> vec;
dfs1(u,u,vec);
reset();
place[x]=1;
for(auto i : vec) place[i]=1;
//cout<<x<<" "<<u<<endl;
if(ask(x,vec[0])==0) return ;
//cout<<x<<" "<<u<<endl;
int l=0,r=vec.size();
while(l+1<r){
int mid=(l+r)>>1;
f(i,0,vec.size()) place[vec[i]]=(i<mid);
if(ask(x,vec[0])==1) r=mid;
else l=mid;
}
vis[vec[l]]=1;
for(auto i : g[vec[l]]){
if(vis[i]==1) continue ;
solve(x,i);
}
if(x<vec[l]) Answer(x,vec[l]);
}
void do_it(int x){
fill(vis,vis+n,0);
vector<int> p;
dfs1(0,0,p);
for(auto u : g[x]){
vis[u]=1;
for(auto v : g[u]){
if(v==x) continue ;
solve(x,v);
}
}
}
void Detect(int T, int _n) {
n=_n;
mark[0]=1;
vector<int> B(1);
f(i,1,n){
if(mark[i]) continue ;
vector<int> vec,A;
mark[i]=1;
f(j,0,n) if(!mark[j]) A.pb(j);
int l=-1,r=A.size();
while(1){
while(l+1<r){
int mid=(l+r)>>1;
reset();
vector<int> p;
dfs1(0,0,p);
place[0]=place[i]=1;
for(auto x : p) place[x]=1;
f(j,0,mid) place[A[j]]=1;
f(j,mid,A.size()) place[A[j]]=mark[A[j]];
if(ask(0,i)==0){
l=mid;
}
else{
r=mid;
}
}
if(l==-1) break;
mark[A[l]]=1;
vec.pb(A[l]);
r=l,l=-1;
}
reset();
vector<int> p;
dfs1(0,0,p);
place[i]=1;
for(auto x : vec) place[x]=1;
l=0,r=p.size();
while(l+1<r){
int mid=(l+r)>>1;
f(j,0,p.size()) place[p[j]]=(j<mid);
if(ask(0,i)==0) l=mid;
else r=mid;
}
//cout<<endl<<i<<" : "<<endl;
//eror(p[l]);
//dbgv(p);
//dbgv(vec);
path(p[l],i,vec);
}
//do_it(2);
f(i,0,n){
do_it(i);
}
}
/*
1
5 4
0 3
3 4
3 1
0 2
1
7 7
0 3
0 5
3 4
3 1
5 2
5 6
1 2
*/