oj.uz

답안 #429644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
429644 2021-06-16T08:16:57 Z Kevin_Zhang_TW Park (JOI17_park) C++17
77 / 100
 234 ms 728 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));
	}

}

void find_graph(int x, vector<int> con) {
	if (con.empty()) return;
	if (qry_list(x, con[0], con) == false) return;

	DE(x);
	debug(AI(con));
	if (con.size() == 1) {
		ans(x, con[0]);
		return;
	}
	int mid = con.size() / 2;
	vector<int> l(begin(con), begin(con)+mid), r(begin(con)+mid, end(con));
	find_graph(x, l), find_graph(x, r);
}
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) {
		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:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
park.cpp:173:2: note: in expansion of macro 'DE'
  173 |  DE(x);
      |  ^~
park.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
park.cpp:174:2: note: in expansion of macro 'debug'
  174 |  debug(AI(con));
      |  ^~~~~
park.cpp: In function 'void make_graph()':
park.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
park.cpp:198:4: note: in expansion of macro 'DE'
  198 |    DE(x, u);
      |    ^~
park.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
park.cpp:200:4: note: in expansion of macro 'debug'
  200 |    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:214:2: note: in expansion of macro 'DE'
  214 |  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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 12 ms 360 KB Output is correct
3 Correct 16 ms 344 KB Output is correct
4 Correct 17 ms 368 KB Output is correct
5 Correct 12 ms 360 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 628 KB Output is correct
2 Correct 179 ms 604 KB Output is correct
3 Correct 133 ms 636 KB Output is correct
4 Correct 136 ms 580 KB Output is correct
5 Correct 153 ms 624 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 516 KB Output is correct
2 Correct 207 ms 588 KB Output is correct
3 Correct 209 ms 560 KB Output is correct
4 Correct 215 ms 584 KB Output is correct
5 Correct 190 ms 524 KB Output is correct
6 Correct 192 ms 584 KB Output is correct
7 Correct 209 ms 520 KB Output is correct
8 Correct 204 ms 668 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 89 ms 632 KB Output is correct
2 Correct 183 ms 592 KB Output is correct
3 Correct 175 ms 644 KB Output is correct
4 Correct 133 ms 652 KB Output is correct
5 Correct 173 ms 728 KB Output is correct
6 Correct 159 ms 624 KB Output is correct
7 Correct 108 ms 580 KB Output is correct
8 Correct 167 ms 580 KB Output is correct
9 Correct 132 ms 588 KB Output is correct
10 Correct 183 ms 508 KB Output is correct
11 Correct 192 ms 708 KB Output is correct
12 Correct 193 ms 612 KB Output is correct
13 Correct 98 ms 580 KB Output is correct
14 Correct 212 ms 580 KB Output is correct
15 Correct 106 ms 592 KB Output is correct
16 Correct 221 ms 584 KB Output is correct
17 Correct 234 ms 548 KB Output is correct
18 Correct 187 ms 708 KB Output is correct
19 Correct 127 ms 624 KB Output is correct
20 Correct 154 ms 580 KB Output is correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 223 ms 580 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -