Submission #1026309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026309		Antekb	Park (JOI17_park)	C++17	100 / 100	213 ms	4688 KiB

park

#include "park.h"
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
const int N=1400;
static int Place[N];
int dist[N], blocked[N];
vi E[N];

bool ask(int a, int b){
	assert(a!=b);
	assert(Place[a]);
	assert(Place[b]);
	return Ask(min(a, b), max(a, b), Place);
}
vector<int> bfs(int root){
	vector<int> V;
	V.push_back(root);
	dist[root]=1;
	for(int i=0; i<V.size(); i++){
		int v=V[i];
		for(int u:E[v]){
			if(!dist[u] && !blocked[u]){
				dist[u]=dist[v]+1;
				V.pb(u);
			}
		}
	}
	return V;
}
void find_edges(int root, int v, bool is_root=0){
	vi V=bfs(root);
	deb(root, v, V);
	for(int i:V)dist[i]=0;
	for(int i:V)Place[i]=1;
	Place[v]=1;
	if(!ask(root, v)){
		assert(!is_root);
		return;
	}
	int l=1, r=SZ(V);
	while(l<r){
		int m=(l+r)/2;
		for(int i=0; i<m; i++){
			Place[V[i]]=1;
		}
		for(int i=m; i<SZ(V); i++){
			Place[V[i]]=0;
		}
		if(ask(root, v))r=m;
		else l=m+1;
	}
	int u=V[l-1];
	E[v].pb(u);
	E[u].pb(v);
	Answer(min(v, u), max(u, v));
	vi rec;
	blocked[u]=1;
	for(int w:E[u]){
		if(!dist[w] && !blocked[w]){
			rec.pb(w);
			bfs(w);
		}
	}
	for(int i:V)dist[i]=0;
	for(int i:V)Place[i]=0;
	Place[v]=0;
	for(int i:rec){
		find_edges(i, v);
	}
	blocked[u]=0;
}

vi gen_chain(int s, int t, vector<int> V){
	deb(s, t, V);
	int l=0, r=V.size();
	while(l<r){
		int m=(l+r)/2;
		for(int i=0; i<m; i++){
			Place[V[i]]=1;
		}
		for(int i=m; i<SZ(V); i++){
			Place[V[i]]=0;
		}
		deb(s, t, Place[s], Place[t]);
		if(ask(s, t))r=m;
		else l=m+1;
	}
	for(int i:V)Place[i]=0;
	if(l==0){
		deb(t);
		return {t};
	}
	else{
		int mid=V[l-1];
		V.resize(l-1);
		Place[mid]=1;
		vi A=gen_chain(s, mid, V);
		vi B=gen_chain(mid, t, V);
		for(int i:B)A.pb(i);
		deb(A);
		return A;
	}
}

void Detect(int T, int n) {
	vector<int> comp, rest;
	comp={0};
	rest.resize(n-1);
	iota(all(rest), 1);
	while(rest.size()){
		int t=rest.back();
		rest.pop_back();
		vi V=bfs(0);
		for(int i:V){
			dist[i]=0;
			Place[i]=1;
		}
		Place[t]=1;
		vector<int> todo=gen_chain(0, t, rest);
		deb(todo);
		for(int i:todo){
			if(i!=t)rest.erase(find(all(rest), i));
			fill(Place, Place+n, 0);
			blocked[i]=1;
			find_edges(0, i, 1);
			blocked[i]=0;
			comp.push_back(i);
		}
		deb(todo);
	}
	for(int i=0; i<n; i++){
		Place[i]=0;
		dist[i]=0;
		blocked[i]=0;
		E[i].clear();
	}
}

Compilation message (stderr)

park.cpp:19:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
park.cpp:19:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
park.cpp:19:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
park.cpp:21:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
park.cpp:21:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~
park.cpp: In function 'std::vector<int> bfs(int)':
park.cpp:45:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i=0; i<V.size(); i++){
      |               ~^~~~~~~~~

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