Submission #594600

#	Time	Username	Problem	Language	Result	Execution time	Memory
594600		Koosha_mv	Park (JOI17_park)	C++14	100 / 100	527 ms	780 KiB

park

#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){
	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

*/

Compilation message (stderr)

park.cpp: In function 'void solve(int, int)':
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   88 |   f(i,0,vec.size()) place[vec[i]]=(i<mid);
      |     ~~~~~~~~~~~~~~             
park.cpp:88:3: note: in expansion of macro 'f'
   88 |   f(i,0,vec.size()) place[vec[i]]=(i<mid);
      |   ^
park.cpp: In function 'void Detect(int, int)':
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
  131 |     f(j,mid,A.size()) place[A[j]]=mark[A[j]];
      |       ~~~~~~~~~~~~~~           
park.cpp:131:5: note: in expansion of macro 'f'
  131 |     f(j,mid,A.size()) place[A[j]]=mark[A[j]];
      |     ^
park.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(int i=a;i<b;i++)
......
  152 |    f(j,0,p.size()) place[p[j]]=(j<mid);
      |      ~~~~~~~~~~~~              
park.cpp:152:4: note: in expansion of macro 'f'
  152 |    f(j,0,p.size()) place[p[j]]=(j<mid);
      |    ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23