oj.uz

Submission #594602

# Submission time Handle Problem Language Result Execution time Memory
594602 2022-07-12T17:38:30 Z Koosha_mv Park (JOI17_park) C++14
100 / 100
 517 ms 756 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);
		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;
	if(ask(x,vec[0])==0) return ;
	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;
		}
		path(p[l],i,vec);
	}
	f(i,0,n){
		do_it(i);
	}
}

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++)
......
   85 |   f(i,0,vec.size()) place[vec[i]]=(i<mid);
      |     ~~~~~~~~~~~~~~             
park.cpp:85:3: note: in expansion of macro 'f'
   85 |   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++)
......
  128 |     f(j,mid,A.size()) place[A[j]]=mark[A[j]];
      |       ~~~~~~~~~~~~~~           
park.cpp:128:5: note: in expansion of macro 'f'
  128 |     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++)
......
  149 |    f(j,0,p.size()) place[p[j]]=(j<mid);
      |      ~~~~~~~~~~~~              
park.cpp:149:4: note: in expansion of macro 'f'
  149 |    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 14 ms 404 KB Output is correct
3 Correct 11 ms 400 KB Output is correct
4 Correct 29 ms 340 KB Output is correct
5 Correct 68 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 652 KB Output is correct
2 Correct 332 ms 468 KB Output is correct
3 Correct 283 ms 604 KB Output is correct
4 Correct 285 ms 508 KB Output is correct
5 Correct 306 ms 712 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 504 KB Output is correct
2 Correct 434 ms 456 KB Output is correct
3 Correct 426 ms 452 KB Output is correct
4 Correct 418 ms 468 KB Output is correct
5 Correct 423 ms 460 KB Output is correct
6 Correct 409 ms 496 KB Output is correct
7 Correct 416 ms 604 KB Output is correct
8 Correct 422 ms 500 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 428 KB Output is correct
2 Correct 442 ms 604 KB Output is correct
3 Correct 434 ms 468 KB Output is correct
4 Correct 411 ms 468 KB Output is correct
5 Correct 396 ms 564 KB Output is correct
6 Correct 386 ms 636 KB Output is correct
7 Correct 326 ms 756 KB Output is correct
8 Correct 408 ms 460 KB Output is correct
9 Correct 387 ms 500 KB Output is correct
10 Correct 379 ms 520 KB Output is correct
11 Correct 406 ms 480 KB Output is correct
12 Correct 420 ms 620 KB Output is correct
13 Correct 346 ms 520 KB Output is correct
14 Correct 410 ms 604 KB Output is correct
15 Correct 352 ms 476 KB Output is correct
16 Correct 433 ms 460 KB Output is correct
17 Correct 235 ms 608 KB Output is correct
18 Correct 421 ms 480 KB Output is correct
19 Correct 326 ms 484 KB Output is correct
20 Correct 417 ms 596 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 512 KB Output is correct
2 Correct 489 ms 468 KB Output is correct
3 Correct 436 ms 456 KB Output is correct
4 Correct 412 ms 468 KB Output is correct
5 Correct 495 ms 492 KB Output is correct
6 Correct 315 ms 600 KB Output is correct
7 Correct 450 ms 520 KB Output is correct
8 Correct 387 ms 564 KB Output is correct
9 Correct 403 ms 468 KB Output is correct
10 Correct 426 ms 604 KB Output is correct
11 Correct 403 ms 544 KB Output is correct
12 Correct 457 ms 592 KB Output is correct
13 Correct 419 ms 452 KB Output is correct
14 Correct 517 ms 496 KB Output is correct
15 Correct 443 ms 604 KB Output is correct
16 Correct 421 ms 464 KB Output is correct
17 Correct 236 ms 612 KB Output is correct
18 Correct 396 ms 472 KB Output is correct