oj.uz

Submission #594600

# Submission time Handle Problem Language Result Execution time Memory
594600 2022-07-12T17:37:16 Z Koosha_mv Park (JOI17_park) C++14
100 / 100
 527 ms 780 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,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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 13 ms 392 KB Output is correct
3 Correct 12 ms 392 KB Output is correct
4 Correct 30 ms 408 KB Output is correct
5 Correct 69 ms 400 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 632 KB Output is correct
2 Correct 342 ms 752 KB Output is correct
3 Correct 295 ms 616 KB Output is correct
4 Correct 304 ms 608 KB Output is correct
5 Correct 307 ms 556 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 448 KB Output is correct
2 Correct 437 ms 492 KB Output is correct
3 Correct 432 ms 488 KB Output is correct
4 Correct 461 ms 496 KB Output is correct
5 Correct 441 ms 468 KB Output is correct
6 Correct 424 ms 460 KB Output is correct
7 Correct 433 ms 468 KB Output is correct
8 Correct 431 ms 456 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 572 KB Output is correct
2 Correct 452 ms 496 KB Output is correct
3 Correct 470 ms 468 KB Output is correct
4 Correct 402 ms 468 KB Output is correct
5 Correct 425 ms 736 KB Output is correct
6 Correct 378 ms 492 KB Output is correct
7 Correct 332 ms 604 KB Output is correct
8 Correct 417 ms 460 KB Output is correct
9 Correct 395 ms 632 KB Output is correct
10 Correct 384 ms 500 KB Output is correct
11 Correct 412 ms 492 KB Output is correct
12 Correct 402 ms 460 KB Output is correct
13 Correct 361 ms 488 KB Output is correct
14 Correct 399 ms 580 KB Output is correct
15 Correct 348 ms 492 KB Output is correct
16 Correct 460 ms 448 KB Output is correct
17 Correct 252 ms 752 KB Output is correct
18 Correct 422 ms 540 KB Output is correct
19 Correct 335 ms 608 KB Output is correct
20 Correct 427 ms 464 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 536 KB Output is correct
2 Correct 504 ms 460 KB Output is correct
3 Correct 468 ms 584 KB Output is correct
4 Correct 419 ms 600 KB Output is correct
5 Correct 527 ms 476 KB Output is correct
6 Correct 307 ms 616 KB Output is correct
7 Correct 466 ms 508 KB Output is correct
8 Correct 399 ms 780 KB Output is correct
9 Correct 419 ms 468 KB Output is correct
10 Correct 440 ms 684 KB Output is correct
11 Correct 442 ms 624 KB Output is correct
12 Correct 465 ms 596 KB Output is correct
13 Correct 426 ms 604 KB Output is correct
14 Correct 516 ms 556 KB Output is correct
15 Correct 466 ms 556 KB Output is correct
16 Correct 419 ms 596 KB Output is correct
17 Correct 259 ms 716 KB Output is correct
18 Correct 406 ms 644 KB Output is correct