Submission #429663

#	Time	Username	Problem	Language	Result	Execution time	Memory
429663		Kevin_Zhang_TW	Park (JOI17_park)	C++17	100 / 100	234 ms	816 KiB

park

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "park.h"

const int MAX_N = 1400;
static int Place[1400];

int n, qcnt;

int mrand(int l, int r) {
	static random_device rd;
	static mt19937 gen(rd());
	return uniform_int_distribution(l, r)(gen);
}

int qry_list(int a, int b, vector<int> go) {
	++qcnt;
	static int ok[MAX_N];
	fill(ok, ok + n, 0);
	for (int i : go) ok[i] = true;
	ok[a] = ok[b] = true;
	if (a > b) swap(a, b);
	return Ask(a, b, ok);
}
int qry_tf(int a, int b, vector<int> go) {
	++qcnt;
	static int ok[MAX_N];
	copy(AI(go), ok);
	ok[a] = ok[b] = true;
	if (a > b) swap(a, b);
	return Ask(a, b, ok);
}

void ans(int a, int b) {
	if (a > b) swap(a, b);
	Answer(a, b);
}
bool on_tree[MAX_N];
vector<int> edge[MAX_N];

vector<int> find_path(int a, int b) {
	vector<int> onpath(n);
	for (int i = 0;i < n;++i) if (!on_tree[i])
		onpath[i] = true;
	onpath[a] = onpath[b] = true;

	vector<int> allon;
	for (int i = 0;i < n;++i) if (i != a && i != b && onpath[i])
		allon.pb(i);

	function<void(vector<int>)> kick = [&](vector<int> all) {
		if (all.empty()) return;
		for (int x : all) onpath[x] = false;
		if (qry_tf(a, b, onpath)) return;
		for (int x : all) onpath[x] = true;
		if (all.size() == 1) return;
		int mid = all.size() / 2;
		vector<int> l(begin(all), begin(all) + mid), r(begin(all) + mid, end(all));
		kick(l), kick(r);
	};
	kick(allon);

//	for (int i = 0;i < n;++i) if (i != a && i != b) {
//		onpath[i] = false;
//		if (!qry_tf(a, b, onpath)) onpath[i] = true;
//	}

	vector<int> path;
	for (int i = 0;i < n;++i) if (i != a && i != b && onpath[i])
		path.pb(i);

	function<void(int, int)> qst = [&](int l, int r) {
		if (r-l+1 <= 1) return;
		int p = mrand(l, r);
		vector<int> lhs, rhs;

		onpath[ path[p] ] = false;

		for (int i = l;i <= r;++i) if (i != p) {
			if (qry_tf(a, path[i], onpath))
				lhs.pb(path[i]);
			else
				rhs.pb(path[i]);
		}

		onpath[ path[p] ] = true;

		int np = lhs.size();

		lhs.pb(path[p]);
		lhs.insert(end(lhs), AI(rhs));
		for (int i = 0, j = l;i < lhs.size();++i) {
			path[j++] = lhs[i];
		}

		qst(l, l + np-1);
		qst(l+np+1, r);
	};

	qst(0, (int) path.size() - 1);

	path.insert(begin(path), a);
	path.insert(end(path), b);

	return path;
}

void add_edge(int a, int b) {
	edge[a].pb(b), edge[b].pb(a);
	ans(a, b);
	DE(a, b);
}
void put_in(vector<int> path) {
	for (int i = 1;i < path.size();++i)
		add_edge(path[i-1], path[i]);
	for (int x : path) on_tree[x] = true;
}

bool done[MAX_N];

vector<int> dfs_order(int x, int lst = -1) {
	static vector<int> stk;
	if (lst == -1) stk.clear();
	stk.pb(x);
	for (int u : edge[x]) if (u != lst && !done[u]) {
		dfs_order(u, x);
	}
	if (lst == -1) return stk;
	return {};
}
void solve_tree() {
	put_in({0});

	for (int i = 0;i < n;++i) if (!on_tree[i]) {
		vector<int> in = dfs_order(0);
		vector<int> out;
		for (int j = 0;j < n;++j) if (!on_tree[j])
			out.pb(j);

		int l = 0, r = (int) in.size() - 1, mid;
		while (l < r) {
			mid = l + r >> 1;
			vector<int> ok = out;
			ok.insert(end(ok), begin(in), begin(in) + mid + 1);
			if (qry_list(0, i, ok))
				r = mid;
			else l = mid+1;
		}
		int p = in[l];
		put_in(find_path(p, i));
	}

}

vector<vector<int>> sep_conp(vector<int> ver) {
	vector<int> vis(n), valid(n);
	for (int x : ver) valid[x] = true;
	vector<vector<int>> ret;

	vector<int> tmp;
	function<void(int)> get_conp = [&](int x) {
		vis[x] = true;
		tmp.pb(x);
		for (int u : edge[x]) if (valid[u] && !vis[u])
			get_conp(u);
	};
	for (int x : ver) if (!vis[x]) {
		get_conp(x);
		ret.pb(tmp);
		tmp.clear();
	}
	return ret;
}
void find_graph(int x, vector<int> con) {
	if (con.empty()) return;
	if (qry_list(x, con[0], con) == false) return;

	int l = 0, r = (int) con.size() - 1, mid;
	auto gv = [&](int len) {
		return vector<int>(begin(con), begin(con)+len);
	};

	while (l < r) {
		mid = l + r >> 1;
		if (qry_list(x, con[0], gv(mid+1)))
			r = mid;
		else
			l = mid+1;
	}
	ans(x, con[l]);
	con.erase(begin(con)+l);

	for (auto vec : sep_conp(con))
		find_graph(x, vec);
}
void make_graph() {
	vector<int> od = dfs_order(0);
	reverse(AI(od)); od.resize(n - 2);

	for (int x : od) {
		int pa = -1;
		for (int u : edge[x]) if (!done[u]) {
			assert(pa == -1);
			pa = u;
		}
		assert(pa != -1);

		done[pa] = done[x] = true;

		for (int u : edge[pa]) if (!done[u]) {
			DE(x, u);
			auto vec = dfs_order(u);
			debug(AI(vec));
			find_graph(x, vec);
			//find_graph(x, dfs_order(u));
		}

//		vector<int> lft = dfs_order(0);
//
//		find_graph(x, lft);

		done[pa] = false;
	}
}
void Detect(int T, int N) {
	n = N;
	DE(N, T);
//	if (T == 1) {
//		for (int i = 0;i < n;++i)
//			for (int j = i+1;j < n;++j)
//				if (qry_list(i, j, {i, j}))
//					ans(i, j);
//		return;
//	}
	solve_tree();
	if (T == 5 || T == 1) {
		make_graph();
	}
}

Compilation message (stderr)

park.cpp: In lambda function:
park.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for (int i = 0, j = l;i < lhs.size();++i) {
      |                         ~~^~~~~~~~~~~~
park.cpp: In function 'void add_edge(int, int)':
park.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
park.cpp:125:2: note: in expansion of macro 'DE'
  125 |  DE(a, b);
      |  ^~
park.cpp: In function 'void put_in(std::vector<int>)':
park.cpp:128:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |  for (int i = 1;i < path.size();++i)
      |                 ~~^~~~~~~~~~~~~
park.cpp: In function 'void solve_tree()':
park.cpp:156:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  156 |    mid = l + r >> 1;
      |          ~~^~~
park.cpp: In function 'void find_graph(int, std::vector<int>)':
park.cpp:198:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  198 |   mid = l + r >> 1;
      |         ~~^~~
park.cpp: In function 'void make_graph()':
park.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
park.cpp:225:4: note: in expansion of macro 'DE'
  225 |    DE(x, u);
      |    ^~
park.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
park.cpp:227:4: note: in expansion of macro 'debug'
  227 |    debug(AI(vec));
      |    ^~~~~
park.cpp: In function 'void Detect(int, int)':
park.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
park.cpp:241:2: note: in expansion of macro 'DE'
  241 |  DE(N, T);
      |  ^~
park.cpp: At global scope:
park.cpp:20:12: warning: 'Place' defined but not used [-Wunused-variable]
   20 | static int Place[1400];
      |            ^~~~~

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