oj.uz

Submission #429602

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

	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:150:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |    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 8 ms 460 KB Output is correct
3 Correct 7 ms 332 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 8 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 556 KB Output is correct
2 Correct 192 ms 616 KB Output is correct
3 Correct 120 ms 568 KB Output is correct
4 Correct 108 ms 560 KB Output is correct
5 Correct 107 ms 608 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 632 KB Output is correct
2 Correct 202 ms 628 KB Output is correct
3 Correct 197 ms 584 KB Output is correct
4 Correct 203 ms 572 KB Output is correct
5 Correct 192 ms 776 KB Output is correct
6 Correct 189 ms 568 KB Output is correct
7 Correct 198 ms 484 KB Output is correct
8 Correct 222 ms 632 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 548 KB Output is correct
2 Correct 172 ms 644 KB Output is correct
3 Correct 195 ms 588 KB Output is correct
4 Correct 136 ms 700 KB Output is correct
5 Correct 161 ms 620 KB Output is correct
6 Correct 124 ms 648 KB Output is correct
7 Correct 105 ms 580 KB Output is correct
8 Correct 158 ms 528 KB Output is correct
9 Correct 121 ms 584 KB Output is correct
10 Correct 170 ms 628 KB Output is correct
11 Correct 184 ms 704 KB Output is correct
12 Correct 195 ms 584 KB Output is correct
13 Correct 83 ms 576 KB Output is correct
14 Correct 197 ms 628 KB Output is correct
15 Correct 80 ms 592 KB Output is correct
16 Correct 195 ms 580 KB Output is correct
17 Correct 208 ms 556 KB Output is correct
18 Correct 166 ms 580 KB Output is correct
19 Correct 109 ms 628 KB Output is correct
20 Correct 155 ms 636 KB Output is correct

Subtask #5
0 / 23.0

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