結果

問題 No.3825 Jump
コンテスト
ユーザー 👑 qand
提出日時 2026-11-22 13:37:40
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 77 ms / 2,000 ms
+ 348µs
コード長 17,318 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,812 ms
コンパイル使用メモリ 397,752 KB
実行使用メモリ 13,824 KB
最終ジャッジ日時 2026-11-22 13:37:53
合計ジャッジ時間 11,522 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge1_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#line 1 "a.cpp"
// https://qandori.github.io/cp-library/
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using std::cin, std::cout, std::cerr;
#define vec vector
#if LONG_MAX == 2147483647L
#undef long
#define long long long
#endif
#define uint unsigned int
#define ulong unsigned long
#define overload3(a, b, c, name, ...) name
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep2(__i__, n)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define per2(i, n) per3(i, 0, n)
#define per1(n) per2(__i__, n)
#define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define CP_ALL_SELECT(first, ...) first
#define CP_ALL_RANGE(a) std::begin(a), std::end(a)
#define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__)
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit()
#define sz(a) static_cast<int>(a.size())
#ifndef DEBUG
#define cerr \
	if (false) cerr
#undef endl
#define endl '\n'
#endif
inline auto operator^=(vector<bool>::reference a, bool b) noexcept {
	if (b) a.flip();
	return a;
}
inline auto operator&=(vector<bool>::reference a, bool b) noexcept {
	if (!b) a = false;
	return a;
}
inline auto operator|=(vector<bool>::reference a, bool b) noexcept {
	if (b) a = true;
	return a;
}
inline ostream &operator<<(ostream &os, __int128_t value) {
	ostream::sentry s(os);
	if (s) {
		__uint128_t tmp = value;
		if (value < 0) tmp = -tmp;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		if (value < 0) --d, *d = '-';
		const int len = std::end(buffer) - d;
		if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit);
	}
	return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
	return os << a.first << ' ' << a.second;
};
template <typename T>
ostream &operator<<(ostream &os, vector<T> a) {
	const int n = a.size();
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &a) {
	return is >> a.first >> a.second;
}
template <typename T, size_t n>
ostream &operator<<(ostream &os, array<T, n> a) {
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &a) {
	for (T &i : a) is >> i;
	return is;
}
template <typename T, typename S>
bool chmin(T &x, S y) {
	if ((T)y < x) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T, typename S>
bool chmax(T &x, S y) {
	if (x < (T)y) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T>
void operator++(vector<T> &a) {
	for (T &i : a) ++i;
}
template <typename T>
void operator--(vector<T> &a) {
	for (T &i : a) --i;
}
template <typename T>
void operator++(vector<T> &a, int) {
	for (T &i : a) i++;
}
template <typename T>
void operator--(vector<T> &a, int) {
	for (T &i : a) i--;
}
void init(), solve();
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
	init();
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
// #define COMB_MAX 1e6
// #include "lib/math/comb.hpp"
// #include "lib/fps/fps.hpp"
// #include "lib/math/mint.hpp"
void init() {}
// 難しくないか??
// 一旦 B スキップ
// 手の震えやばいよ〜
// ゲームですねえ
// 上に貪欲に進んでいくのが正答っぽい
// 毎回愚直にやって間に合うか?
// 間に合いそう
// 実は lca 以外の情報は切り落とせますね
// そっからどうしよう
#line 1 "lib/tree/lca.hpp"



#line 1 "lib/components/static_range_min.hpp"



#line 1 "lib/components/default_init_allocator.hpp"



#line 6 "lib/components/default_init_allocator.hpp"

template <class T>
struct DefaultInitAllocator : std::allocator<T> {
	template <class U>
	struct rebind {
		using other = DefaultInitAllocator<U>;
	};
	DefaultInitAllocator() = default;
	template <class U>
	DefaultInitAllocator(const DefaultInitAllocator<U> &) noexcept {}
	template <class U>
	void construct(U *p) { ::new (static_cast<void *>(p)) U; }
};


#line 1 "lib/data_structure/sparse_table.hpp"



#line 6 "lib/data_structure/sparse_table.hpp"
#include <bit>
#line 11 "lib/data_structure/sparse_table.hpp"
#include <type_traits>
#line 14 "lib/data_structure/sparse_table.hpp"

template <class S, auto op, auto e = nullptr>
class SparseTable {
	using Value = std::conditional_t<std::is_same_v<S, bool>, std::uint8_t, S>;
	using Reference = std::conditional_t<std::is_same_v<S, bool>, bool, const S &>;
	int n = 0;
	std::vector<std::vector<Value, DefaultInitAllocator<Value>>> data;
	static decltype(auto) combine(const Value &a, const Value &b) {
		if constexpr (std::is_same_v<S, bool> || !std::is_invocable_v<decltype(op), const S &, const S &>) return S(op(S(a), S(b)));
		else return op(a, b);
	}

  public:
	SparseTable() = default;
	SparseTable(const SparseTable &) = default;
	SparseTable &operator=(const SparseTable &) = default;
	SparseTable(SparseTable &&other) noexcept : n(std::exchange(other.n, 0)), data(std::move(other.data)) {}
	SparseTable &operator=(SparseTable &&other) noexcept {
		if (this != &other) {
			n = std::exchange(other.n, 0);
			data = std::move(other.data);
		}
		return *this;
	}
	explicit SparseTable(const std::vector<S> &a) { build(a); }
	void clear() {
		data.clear();
		n = 0;
	}
	void build(const std::vector<S> &a) {
		assert(a.size() <= std::size_t(std::numeric_limits<int>::max()));
		build(static_cast<int>(a.size()), [&](int i) -> S { return a[i]; });
	}
	template <class F>
	void build(int size, F value) {
		assert(size >= 0);
		n = size;
		data.resize(std::bit_width(unsigned(n)));
		if (!n) return;
		if constexpr (std::is_default_constructible_v<Value>) {
			data[0].resize(n);
			for (int i = 0; i < n; ++i) data[0][i] = value(i);
		} else {
			data[0].clear();
			data[0].reserve(n);
			for (int i = 0; i < n; ++i) data[0].push_back(value(i));
		}
		for (int k = 1; k < std::bit_width(unsigned(n)); ++k) {
			int length = n - (1U << k) + 1, half = 1U << (k - 1);
			if constexpr (std::is_default_constructible_v<Value>) {
				data[k].resize(length);
				for (int i = 0; i < length; ++i) data[k][i] = combine(data[k - 1][i], data[k - 1][i + half]);
			} else {
				data[k].clear();
				data[k].reserve(length);
				for (int i = 0; i < length; ++i) data[k].push_back(combine(data[k - 1][i], data[k - 1][i + half]));
			}
		}
	}
	int size() const { return n; }
	bool empty() const { return n == 0; }
	Reference operator[](int i) const {
		assert(0 <= i && i < n);
		return data[0][i];
	}
	[[gnu::always_inline]] S prod(int l, int r) const {
		assert(0 <= l && l <= r && r <= n);
		if constexpr (std::is_same_v<decltype(e), std::nullptr_t>) assert(l < r);
		else if (l == r) return e();
		return prod_unchecked(l, r);
	}
	[[gnu::always_inline]] S prod_unchecked(int l, int r) const {
		int k = std::bit_width(unsigned(r - l)) - 1;
		return combine(data[k][l], data[k][r - (1U << k)]);
	}
	S all_prod() const { return prod(0, n); }
};


#line 12 "lib/components/static_range_min.hpp"
#include <span>
#line 16 "lib/components/static_range_min.hpp"

template <class T = int, bool FastBoundaries = false> class StaticRangeMin {
	static T minimum(T a, T b) { return b < a ? b : a; }
	std::vector<T> values_;
	std::vector<std::uint32_t, DefaultInitAllocator<std::uint32_t>> masks_;
	SparseTable<T, minimum> blocks_;
	struct Boundaries { std::vector<T> prefix, suffix; };
	struct Empty {};
	[[no_unique_address]] std::conditional_t<FastBoundaries, Boundaries, Empty> boundaries_;
	T within(int l, int r) const {
		auto mask = masks_[r - 1] & (~std::uint32_t(0) << (l & 31));
		return values_[(l & ~31) + std::countr_zero(mask)];
	}

  public:
	StaticRangeMin() = default;
	explicit StaticRangeMin(std::vector<T> values) { build(std::move(values)); }
	void build(std::vector<T> values) {
		assert(values.size() <= std::size_t(std::numeric_limits<int>::max()));
		values_ = std::move(values);
		int n = size();
		masks_.resize(n);
		for (int first = 0; first < n;) {
			int last = first + std::min(32, n - first);
			std::uint32_t mask = 0;
			for (int i = first; i < last; ++i) {
				while (mask && !(values_[first + std::bit_width(mask) - 1] < values_[i]))
					mask &= ~(std::uint32_t(1) << (std::bit_width(mask) - 1));
				mask |= std::uint32_t(1) << (i - first);
				masks_[i] = mask;
			}
			first = last;
		}
		if constexpr (FastBoundaries) {
			boundaries_.prefix = values_, boundaries_.suffix = values_;
			for (int first = 0; first < n;) {
				int last = first + std::min(32, n - first);
				for (int i = first + 1; i < last; ++i) boundaries_.prefix[i] = minimum(boundaries_.prefix[i - 1], values_[i]);
				for (int i = last - 1; i > first; --i) boundaries_.suffix[i - 1] = minimum(values_[i - 1], boundaries_.suffix[i]);
				first = last;
			}
		}
		blocks_.build(n ? (n - 1) / 32 + 1 : 0, [&](int i) {
			int last = i * 32 + std::min(32, n - i * 32);
			if constexpr (FastBoundaries) return T(boundaries_.prefix[last - 1]);
			else return within(i * 32, last);
		});
	}
	int size() const { return static_cast<int>(values_.size()); }
	bool empty() const { return values_.empty(); }
	std::conditional_t<std::is_same_v<T, bool>, bool, const T &> operator[](int i) const {
		assert(0 <= i && i < size());
		return values_[i];
	}
	T prod(int l, int r) const {
		assert(0 <= l && l < r && r <= size());
		int a = l / 32, b = (r - 1) / 32;
		if (a == b) return within(l, r);
		T value = [&] {
			if constexpr (FastBoundaries) return minimum(boundaries_.suffix[l], boundaries_.prefix[r - 1]);
			else return minimum(within(l, (a + 1) * 32), within(b * 32, r));
		}();
		if (a + 1 < b) value = minimum(value, blocks_.prod_unchecked(a + 1, b));
		return value;
	}
	std::vector<T> prod_many(std::span<const std::pair<int, int>> ranges) const {
		std::vector<T> result;
		result.reserve(ranges.size());
		if constexpr (FastBoundaries) {
			for (auto [l, r] : ranges) result.emplace_back(prod(l, r));
		} else {
			std::array<int, 32> left, right;
			for (std::size_t first = 0; first < ranges.size(); first += 32) {
				int count = int(std::min<std::size_t>(32, ranges.size() - first));
				auto [sample_l, sample_r] = ranges[first];
				assert(0 <= sample_l && sample_l < sample_r && sample_r <= size());
				bool wide = std::is_integral_v<T> && sample_r - sample_l >= 256;
				if (wide) {
					int a = sample_l / 32, b = (sample_r - 1) / 32;
					T middle = blocks_.prod_unchecked(a + 1, b);
					wide = !(blocks_[a] < middle) && !(blocks_[b] < middle);
				}
				for (int i = 1; i < count && wide; ++i) wide = ranges[first + i].second - ranges[first + i].first >= 256;
				if (wide) {
					for (int i = 0; i < count; ++i) {
						auto [l, r] = ranges[first + i];
						assert(0 <= l && l < r && r <= size());
						int a = l / 32, b = (r - 1) / 32;
						T value = blocks_.prod_unchecked(a + 1, b);
						if (blocks_[a] < value) value = minimum(value, within(l, (a + 1) * 32));
						if (blocks_[b] < value) value = minimum(value, within(b * 32, r));
						result.emplace_back(std::move(value));
					}
					continue;
				}
				for (int i = 0; i < count; ++i) {
					auto [l, r] = ranges[first + i];
					assert(0 <= l && l < r && r <= size());
					int a = l & ~31, b = (r - 1) & ~31;
					auto mask = masks_[a == b ? r - 1 : a + 31] & (~std::uint32_t(0) << (l & 31));
					left[i] = a + std::countr_zero(mask);
					right[i] = a == b ? left[i] : b + std::countr_zero(masks_[r - 1]);
#if defined(__GNUC__) || defined(__clang__)
					if constexpr (!std::is_same_v<T, bool>) {
						__builtin_prefetch(values_.data() + left[i]);
						__builtin_prefetch(values_.data() + right[i]);
					}
#endif
				}
				for (int i = 0; i < count; ++i) {
					auto [l, r] = ranges[first + i];
					T value = minimum(values_[left[i]], values_[right[i]]);
					int a = l / 32 + 1, b = (r - 1) / 32;
					if (a < b) value = minimum(value, blocks_.prod_unchecked(a, b));
					result.emplace_back(std::move(value));
				}
			}
		}
		return result;
	}

	T all_prod() const { return prod(0, size()); }
};


#line 11 "lib/tree/lca.hpp"

class LCA {
	std::vector<int> in, out, order;
	bool ordered_ = false;
	StaticRangeMin<int, true> table;
	void check([[maybe_unused]] int v) const { assert(0 <= v && v < n && static_cast<int>(in.size()) == n); }

	template<bool Ordered = false> void finish(int root) {
		in[root] = n;
		ordered_ = root == 0;
		for (int i = n - 2; i >= 0; --i) {
			int v = Ordered ? n - 1 - i : order[i], p = parent[v];
			depth[v] = depth[p] + 1;
			in[v] = in[p];
			in[p] -= out[v];
		}
		std::vector<int> values(n);
		for (int v = 0; v < n; ++v) {
			--in[v];
			out[v] += in[v];
			order[in[v]] = v;
			if constexpr (Ordered) values[in[v]] = v ? parent[v] : 0;
			else ordered_ &= parent[v] < v;
		}
		if constexpr (!Ordered)
			for (int i = 1; i < n; ++i) values[i] = ordered_ ? parent[order[i]] : in[parent[order[i]]];
		table.build(std::move(values));
		parent[root] = -1;
	}

  public:
	int n;
	std::vector<std::pair<int, int>> edges;
	std::vector<int> parent, depth;
	explicit LCA(int n = 0) : n(n) {
		assert(0 <= n && n <= std::numeric_limits<int>::max() / 2);
		edges.reserve(std::max(0, n - 1));
	}
	int add_edge(int u, int v) {
		assert(0 <= u && u < n && 0 <= v && v < n);
		edges.emplace_back(u, v);
		return static_cast<int>(edges.size()) - 1;
	}
	void build(int root = 0) {
		assert(n >= 0 && edges.size() == std::size_t(std::max(0, n - 1)));
		assert(!n || (0 <= root && root < n));
		in.resize(n);
		out.resize(n);
		order.resize(n);
		parent.assign(n, -1);
		depth.assign(n, 0);
		table = StaticRangeMin<int, true>();
		if (!n) return;
		std::vector<int> degree(n), neighbors(n);
		for (auto [u, v] : edges) {
			++degree[u], ++degree[v];
			neighbors[u] ^= v, neighbors[v] ^= u;
		}
		degree[root] += 2;
		std::fill(out.begin(), out.end(), 1);
		int count = 0;
		for (int v = 0; v < n; ++v) if (degree[v] == 1) order[count++] = v;
		for (int i = 0; i < count; ++i) {
			int v = order[i], p = neighbors[v];
			parent[v] = p;
			out[p] += out[v];
			neighbors[p] ^= v;
			if (--degree[p] == 1) order[count++] = p;
		}
		assert(count == n - 1);
		finish(root);
	}

	void build_from_parents(std::vector<int> parents) {
		assert(parents.size() <= std::size_t(std::numeric_limits<int>::max() / 2));
		n = static_cast<int>(parents.size());
		parent = std::move(parents);
		in.resize(n);
		out.assign(n, 1);
		order.resize(n);
		depth.assign(n, 0);
		table = StaticRangeMin<int, true>();
		edges.clear();
		edges.reserve(std::max(0, n - 1));
		if (!n) return;
		int root = -1;
		bool ordered = true;
		for (int v = 0; v < n; ++v) {
			int p = parent[v];
			assert(-1 <= p && p < n && p != v);
			if (p == -1) {
				assert(root == -1);
				root = v;
			} else {
				edges.emplace_back(p, v);
				ordered &= p < v;
			}
		}
		assert(root != -1);
		if (ordered) {
			for (int v = n - 1; v > 0; --v) {
				out[parent[v]] += out[v];
			}
			finish<true>(root);
			return;
		} else {
			std::fill(in.begin(), in.end(), 0);
			for (int v = 0; v < n; ++v) if (v != root) ++in[parent[v]];
			int count = 0;
			for (int v = 0; v < n; ++v) if (!in[v] && v != root) order[count++] = v;
			for (int i = 0; i < count; ++i) {
				int v = order[i], p = parent[v];
				out[p] += out[v];
				if (!--in[p] && p != root) order[count++] = p;
			}
			assert(count == n - 1);
		}
		finish(root);
	}

	int lca(int u, int v) const {
		check(u);
		check(v);
		int l = in[u], r = in[v];
		if (l == r) return u;
		if (l > r) std::swap(l, r);
		++l;
		int w = table.prod(l, r + 1);
		return ordered_ ? w : order[w];
	}
	int dist(int u, int v) const {
		int w = lca(u, v);
		return depth[u] + depth[v] - 2 * depth[w];
	}
	int distance(int u, int v) const { return dist(u, v); }
	bool is_ancestor(int u, int v) const {
		check(u);
		check(v);
		return in[u] <= in[v] && in[v] < out[u];
	}
	std::pair<int, int> subtree(int v) const {
		check(v);
		return {in[v], out[v]};
	}
};


#line 151 "a.cpp"
void solve_() { // 実験を書き始めるのが遅い
	// 愚直すらバグらせてしまう
	int n;
	cin >> n;
	vec<vec<int>> a(n, vec<int>(n));
	auto f = [&](this auto f, int x, int y) -> int {
		if (x <= y) return a[x][y] = 1;
		if (y == 0) return a[x][y] = -1;
		if (a[x][y] != 0) return a[x][y];
		const int c = (x - y + 1) / 2;
		return a[x][y] = -f(y, c);
	};
	rep(i, n) rep(j, n) f(i, j);
	for (auto &aa : a) {
		for (int v : aa) cout << (v == 1 ? "#" : ".");
		cout << endl;
	}
	// これ愚直でも間に合う?
	// 間に合う雰囲気
}
void solve() {
	int n;
	cin >> n;
	auto lca = LCA(n);
	rep(i, n - 1) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		lca.add_edge(u, v);
	}
	lca.build();
	int que;
	cin >> que;
	auto g = [&](this auto g, int x, int y) -> int {
		if (x <= y) return 1;
		if (y == 0) return -1;
		const int c = (x - y + 1) / 2;
		return -g(y, c);
	};
	while (que--) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		const int u = lca.lca(a, b);
		const int aa = lca.dist(u, a), bb = lca.dist(u, b);
		// cerr << "! " << aa << " " << bb << endl;
		cout << (g(aa, bb) == 1 ? "Alice" : "Bob") << endl;
	}
}
0