oj.uz

Submission #429663

# Submission time Handle Problem Language Result Execution time Memory
429663 2021-06-16T08:33:49 Z Kevin_Zhang_TW Park (JOI17_park) C++17
100 / 100
 234 ms 816 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 7 ms 396 KB Output is correct
3 Correct 6 ms 452 KB Output is correct
4 Correct 14 ms 592 KB Output is correct
5 Correct 30 ms 556 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 632 KB Output is correct
2 Correct 175 ms 604 KB Output is correct
3 Correct 138 ms 600 KB Output is correct
4 Correct 121 ms 680 KB Output is correct
5 Correct 104 ms 624 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 616 KB Output is correct
2 Correct 187 ms 704 KB Output is correct
3 Correct 183 ms 672 KB Output is correct
4 Correct 199 ms 652 KB Output is correct
5 Correct 173 ms 584 KB Output is correct
6 Correct 179 ms 596 KB Output is correct
7 Correct 191 ms 536 KB Output is correct
8 Correct 185 ms 708 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 540 KB Output is correct
2 Correct 186 ms 592 KB Output is correct
3 Correct 164 ms 520 KB Output is correct
4 Correct 111 ms 580 KB Output is correct
5 Correct 173 ms 616 KB Output is correct
6 Correct 122 ms 580 KB Output is correct
7 Correct 91 ms 528 KB Output is correct
8 Correct 148 ms 592 KB Output is correct
9 Correct 116 ms 568 KB Output is correct
10 Correct 161 ms 628 KB Output is correct
11 Correct 174 ms 652 KB Output is correct
12 Correct 170 ms 612 KB Output is correct
13 Correct 84 ms 488 KB Output is correct
14 Correct 182 ms 528 KB Output is correct
15 Correct 78 ms 580 KB Output is correct
16 Correct 188 ms 620 KB Output is correct
17 Correct 212 ms 580 KB Output is correct
18 Correct 165 ms 680 KB Output is correct
19 Correct 111 ms 748 KB Output is correct
20 Correct 137 ms 576 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 700 KB Output is correct
2 Correct 218 ms 600 KB Output is correct
3 Correct 231 ms 636 KB Output is correct
4 Correct 190 ms 580 KB Output is correct
5 Correct 234 ms 660 KB Output is correct
6 Correct 151 ms 708 KB Output is correct
7 Correct 177 ms 652 KB Output is correct
8 Correct 199 ms 664 KB Output is correct
9 Correct 204 ms 660 KB Output is correct
10 Correct 197 ms 580 KB Output is correct
11 Correct 160 ms 716 KB Output is correct
12 Correct 151 ms 612 KB Output is correct
13 Correct 187 ms 596 KB Output is correct
14 Correct 224 ms 580 KB Output is correct
15 Correct 205 ms 580 KB Output is correct
16 Correct 216 ms 816 KB Output is correct
17 Correct 233 ms 652 KB Output is correct
18 Correct 207 ms 580 KB Output is correct