結果
| 問題 | No.3825 Jump |
| コンテスト | |
| ユーザー |
👑 |
| 提出日時 | 2026-11-22 13:37:40 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 77 ms / 2,000 ms |
| + 348µs | |
| コード長 | 17,318 bytes |
| 記録 | |
| コンパイル時間 | 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 |
ソースコード
#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;
}
}