oj.uz

Submission #594593

# Submission time Handle Problem Language Result Execution time Memory
594593 2022-07-12T17:29:52 Z Koosha_mv Park (JOI17_park) C++14
67 / 100
 441 ms 856 KB 
#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,par[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 ;
		par[u]=v;
		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 || par[vec[l]]==i) continue ;
		solve(x,i);
	}
	if(l>0){
		solve(x,u);
	}
	if(x<vec[l]) Answer(x,vec[l]);
}
void do_it(int x){
	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;
				fill(vis,vis+n,0);
				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;
		fill(vis,vis+n,0);
		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

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++)
......
   90 |   f(i,0,vec.size()) place[vec[i]]=(i<mid);
      |     ~~~~~~~~~~~~~~             
park.cpp:90:3: note: in expansion of macro 'f'
   90 |   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++)
......
  134 |     f(j,mid,A.size()) place[A[j]]=mark[A[j]];
      |       ~~~~~~~~~~~~~~           
park.cpp:134:5: note: in expansion of macro 'f'
  134 |     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++)
......
  156 |    f(j,0,p.size()) place[p[j]]=(j<mid);
      |      ~~~~~~~~~~~~              
park.cpp:156:4: note: in expansion of macro 'f'
  156 |    f(j,0,p.size()) place[p[j]]=(j<mid);
      |    ^

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 856 KB Output is correct
2 Correct 333 ms 616 KB Output is correct
3 Correct 294 ms 608 KB Output is correct
4 Correct 256 ms 696 KB Output is correct
5 Correct 268 ms 544 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 616 KB Output is correct
2 Correct 435 ms 492 KB Output is correct
3 Correct 416 ms 488 KB Output is correct
4 Correct 411 ms 448 KB Output is correct
5 Correct 424 ms 460 KB Output is correct
6 Correct 418 ms 484 KB Output is correct
7 Correct 413 ms 488 KB Output is correct
8 Correct 420 ms 596 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 588 KB Output is correct
2 Correct 420 ms 468 KB Output is correct
3 Correct 441 ms 732 KB Output is correct
4 Correct 372 ms 588 KB Output is correct
5 Correct 393 ms 616 KB Output is correct
6 Correct 360 ms 572 KB Output is correct
7 Correct 319 ms 620 KB Output is correct
8 Correct 403 ms 600 KB Output is correct
9 Correct 381 ms 468 KB Output is correct
10 Correct 371 ms 592 KB Output is correct
11 Correct 381 ms 476 KB Output is correct
12 Correct 403 ms 596 KB Output is correct
13 Correct 342 ms 472 KB Output is correct
14 Correct 395 ms 468 KB Output is correct
15 Correct 330 ms 640 KB Output is correct
16 Correct 420 ms 484 KB Output is correct
17 Correct 189 ms 592 KB Output is correct
18 Correct 384 ms 632 KB Output is correct
19 Correct 312 ms 468 KB Output is correct
20 Correct 401 ms 476 KB Output is correct

Subtask #5
0 / 23.0

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