oj.uz

Submission #429607

# Submission time Handle Problem Language Result Execution time Memory
429607 2021-06-16T07:41:23 Z Kevin_Zhang_TW Park (JOI17_park) C++17
77 / 100
 222 ms 724 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;

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) {
	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) {
	static int ok[MAX_N];
	copy(AI(go), ok);
	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);
}
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;
}
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) {
		dfs_order(u, x);
	}
	if (lst == -1) return stk;
	return {};
}
void solve_tree() {
	//vector<int> abp = find_path(0, 1);
	//put_in(abp);
	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));
	}

}
void Detect(int T, int N) {
	n = N;

	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;
	}
//
//	if (T == 2) {
//		auto a = find_path(0, N-1);
//
//		for (int i = 1;i < N;++i)
//			ans(a[i-1], a[i]);
//		return;
//	}
//
	if (T <= 4) {
		solve_tree();
	}
}

Compilation message

park.cpp: In lambda function:
park.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for (int i = 0, j = l;i < lhs.size();++i) {
      |                         ~~^~~~~~~~~~~~
park.cpp: In function 'void put_in(std::vector<int>)':
park.cpp:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for (int i = 1;i < path.size();++i)
      |                 ~~^~~~~~~~~~~~~
park.cpp: In function 'void solve_tree()':
park.cpp:151:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  151 |    mid = l + r >> 1;
      |          ~~^~~
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 9 ms 332 KB Output is correct
3 Correct 12 ms 360 KB Output is correct
4 Correct 11 ms 332 KB Output is correct
5 Correct 11 ms 360 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 644 KB Output is correct
2 Correct 173 ms 576 KB Output is correct
3 Correct 121 ms 652 KB Output is correct
4 Correct 123 ms 548 KB Output is correct
5 Correct 128 ms 644 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 564 KB Output is correct
2 Correct 201 ms 576 KB Output is correct
3 Correct 202 ms 572 KB Output is correct
4 Correct 218 ms 708 KB Output is correct
5 Correct 201 ms 612 KB Output is correct
6 Correct 222 ms 580 KB Output is correct
7 Correct 198 ms 504 KB Output is correct
8 Correct 219 ms 592 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 528 KB Output is correct
2 Correct 203 ms 544 KB Output is correct
3 Correct 182 ms 572 KB Output is correct
4 Correct 116 ms 580 KB Output is correct
5 Correct 168 ms 620 KB Output is correct
6 Correct 129 ms 588 KB Output is correct
7 Correct 117 ms 500 KB Output is correct
8 Correct 163 ms 664 KB Output is correct
9 Correct 123 ms 576 KB Output is correct
10 Correct 172 ms 724 KB Output is correct
11 Correct 186 ms 636 KB Output is correct
12 Correct 185 ms 604 KB Output is correct
13 Correct 86 ms 492 KB Output is correct
14 Correct 193 ms 632 KB Output is correct
15 Correct 79 ms 580 KB Output is correct
16 Correct 198 ms 628 KB Output is correct
17 Correct 195 ms 520 KB Output is correct
18 Correct 171 ms 616 KB Output is correct
19 Correct 111 ms 504 KB Output is correct
20 Correct 155 ms 524 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -