結果
| 問題 | No.3825 Jump |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-22 13:49:15 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 597 ms / 2,000 ms |
| + 841µs | |
| コード長 | 18,919 bytes |
| 記録 | |
| コンパイル時間 | 3,981 ms |
| コンパイル使用メモリ | 363,824 KB |
| 実行使用メモリ | 157,076 KB |
| 最終ジャッジ日時 | 2026-11-22 13:49:38 |
| 合計ジャッジ時間 | 22,573 ms |
|
ジャッジサーバーID (参考情報) |
judge5_0 / judge6_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
ソースコード
// SPDX-License-Identifier: CC0-1.0
//
// [English]
// To the extent possible under law, the author(s) have dedicated all copyright
// and related and neighboring rights to this software to the public domain
// worldwide. This software is distributed without any warranty.
// See <https://creativecommons.org/publicdomain/zero/1.0/> for details.
//
// [日本語]
// 法律上可能な範囲で、著作者はこのソフトウェアに関する著作権および
// 著作隣接権を含むすべての関連する権利を、全世界でパブリックドメインに
// 提供しています。本ソフトウェアは一切の保証なく配布されます。
// 自由にコピー・改変・再配布・商用利用できます(クレジット表記は不要です)。
// 詳細は <https://creativecommons.org/publicdomain/zero/1.0/deed.ja> を参照してください。
// ※ 英語の文面および CC0 1.0 の正式な条文(英語)が優先されます。
#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;
#include <atcoder/all>
using mint=atcoder::modint998244353;
ostream& operator<<(ostream& os,const mint& x){
os<<x.val();
return os;
}
istream& operator>>(istream& is,mint& x){
int t;
is>>t;
x=t;
return is;
}
template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p);
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p);
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr);
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr);
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec);
template <typename T>
istream& operator>>(istream& is,vector<T>& vec);
template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p){
os<<p.first<<" "<<p.second;
return os;
}
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p){
is>>p.first>>p.second;
return is;
}
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr){
for(int i=0;i<n;i++)os<<arr[i]<<(i+1==n?"":" ");
return os;
}
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr){
for(int i=0;i<n;i++)is>>arr[i];
return is;
}
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
for(int i=0;i<(int)vec.size();i++)os<<vec[i]<<(i+1==(int)vec.size()?"":" ");
return os;
}
template <typename T>
istream& operator>>(istream& is,vector<T>& vec){
for(int i=0;i<(int)vec.size();i++)is>>vec[i];
return is;
}
template<class... Vecs>
void input_vec(Vecs&... vs) {
const auto n = get<0>(tie(vs...)).size();
for (size_t i = 0; i < n; ++i)
((cin >> vs[i]), ...);
}
template <class... Vecs>
void output_vec(const Vecs&... vs) {
const auto n = get<0>(tie(vs...)).size();
for (size_t i = 0; i < n; ++i) {
bool first = true;
(((cout << (exchange(first, false) ? "" : " ") << vs[i])), ...);
cout << endl;
}
}
template <typename C>
C make_unique(C vec){
ranges::sort(vec);
vec.erase(unique(vec.begin(),vec.end()),vec.end());
return vec;
}
vector<int> Iota(int n,int s=0){
vector<int> res(n);
iota(res.begin(),res.end(),s);
return res;
}
vector<ll> Iotall(int n,ll s=0){
vector<ll> res(n);
iota(res.begin(),res.end(),s);
return res;
}
void YESNO(bool f){
if(f)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vvvi=vector<vector<vector<int>>>;
using vmi=vector<mint>;
using vvmi=vector<vector<mint>>;
using vvvmi=vector<vector<vector<mint>>>;
//https://atcoder.jp/contests/awc0150/submissions/79608947
// generated by ChatGPT outside of contest time.
#include <algorithm>
#include <cassert>
#include <vector>
template <class S, S (*op)(S, S), S (*e)()>
struct disjoint_sparse_table {
public:
disjoint_sparse_table() : disjoint_sparse_table(0) {}
explicit disjoint_sparse_table(int n)
: disjoint_sparse_table(std::vector<S>(n, e())) {}
explicit disjoint_sparse_table(const std::vector<S>& v)
: _n((int)v.size()), data_(v) {
log_ = 0;
while ((1LL << log_) < _n) ++log_;
table_.assign(log_, std::vector<S>(_n, e()));
for (int k = 0; k < log_; ++k) {
const long long half = 1LL << k;
const long long block = half << 1;
for (long long l = 0; l < _n; l += block) {
const int m =
(int)std::min<long long>(l + half, _n);
const int r =
(int)std::min<long long>(l + block, _n);
// 左半分: suffix
if ((int)l < m) {
table_[k][m - 1] = data_[m - 1];
for (int i = m - 2; i >= (int)l; --i) {
table_[k][i] =
op(data_[i], table_[k][i + 1]);
}
}
// 右半分: prefix
if (m < r) {
table_[k][m] = data_[m];
for (int i = m + 1; i < r; ++i) {
table_[k][i] =
op(table_[k][i - 1], data_[i]);
}
}
}
}
}
S get(int p) const {
assert(0 <= p && p < _n);
return data_[p];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
if (l + 1 == r) return data_[l];
const unsigned x =
static_cast<unsigned>(l ^ (r - 1));
const int k = 31 - __builtin_clz(x);
return op(table_[k][l], table_[k][r - 1]);
}
S all_prod() const {
return prod(0, _n);
}
template <bool (*f)(S)>
int max_right(int l) const {
return max_right(l, f);
}
template <class F>
int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
if (f(prod(l, _n))) return _n;
int ok = l;
int ng = _n;
while (ng - ok > 1) {
const int m = ok + (ng - ok) / 2;
if (f(prod(l, m))) {
ok = m;
} else {
ng = m;
}
}
return ok;
}
template <bool (*f)(S)>
int min_left(int r) const {
return min_left(r, f);
}
template <class F>
int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
if (f(prod(0, r))) return 0;
int ng = 0;
int ok = r;
while (ok - ng > 1) {
const int m = ng + (ok - ng) / 2;
if (f(prod(m, r))) {
ok = m;
} else {
ng = m;
}
}
return ok;
}
private:
int _n;
int log_;
std::vector<S> data_;
std::vector<std::vector<S>> table_;
};
//https://atcoder.jp/contests/awc0150/submissions/79608947
// generated by ChatGPT outside of contest time.
#include <algorithm>
#include <cassert>
#include <limits>
#include <utility>
#include <vector>
namespace tree_lca_detail {
using rmq_value = std::pair<long long, int>;
// {depth, vertex}
inline rmq_value rmq_op(rmq_value a, rmq_value b) {
return std::min(a, b);
}
inline rmq_value rmq_e() {
return {
std::numeric_limits<long long>::max(),
std::numeric_limits<int>::max()
};
}
} // namespace tree_lca_detail
class tree_lca {
using rmq_value = tree_lca_detail::rmq_value;
using dst_type =
disjoint_sparse_table<
rmq_value,
tree_lca_detail::rmq_op,
tree_lca_detail::rmq_e>;
public:
struct auxiliary_tree {
struct edge {
int to;
long long length;
};
// Auxiliary Tree 上での根
int root = -1;
// 無向隣接リスト
std::vector<std::vector<edge>> graph;
// compressed vertex -> original vertex
//
// 元の頂点番号の昇順になっている。
std::vector<int> vertex;
// root を根としたときの親
std::vector<int> parent;
// parent との辺の長さ
std::vector<long long> parent_edge_length;
// 元々 make_auxiliary_tree() に渡された頂点なら true
std::vector<char> is_terminal;
int size() const {
return (int)vertex.size();
}
int original_vertex(int v) const {
assert(0 <= v && v < size());
return vertex[v];
}
/*
* original vertex -> compressed vertex
*
* Auxiliary Tree に含まれなければ -1
*
* O(log |V_aux|)
*/
int compressed_id(int v) const {
auto it =
std::lower_bound(vertex.begin(), vertex.end(), v);
if (it == vertex.end() || *it != v) {
return -1;
}
return (int)(it - vertex.begin());
}
};
explicit tree_lca(
const std::vector<std::vector<int>>& graph,
int root = 0
)
: n_((int)graph.size()),
root_(root),
depth_(n_),
first_(n_, -1),
parent_(n_, -1) {
assert(n_ > 0);
assert(0 <= root_ && root_ < n_);
/*
* Euler Tour
*
* tour[i] = {depth, vertex}
*
* 再帰 DFS を避けている。
*/
std::vector<rmq_value> tour;
tour.reserve(2 * n_ - 1);
struct frame {
int v;
int p;
int next;
};
std::vector<frame> stack;
stack.reserve(n_);
depth_[root_] = 0;
parent_[root_] = -1;
first_[root_] = 0;
tour.push_back({0, root_});
stack.push_back({root_, -1, 0});
while (!stack.empty()) {
frame& f = stack.back();
// v の全ての子を処理し終えた
if (f.next == (int)graph[f.v].size()) {
stack.pop_back();
// 親へ戻る
if (!stack.empty()) {
int p = stack.back().v;
tour.push_back({depth_[p], p});
}
continue;
}
int to = graph[f.v][f.next++];
if (to == f.p) continue;
parent_[to] = f.v;
depth_[to] = depth_[f.v] + 1;
first_[to] = (int)tour.size();
tour.push_back({depth_[to], to});
stack.push_back({to, f.v, 0});
}
rmq_ = dst_type(tour);
}
template <typename T>
explicit tree_lca(
const std::vector<std::vector<std::pair<T,int>>>& graph,
int root = 0
)
: n_((int)graph.size()),
root_(root),
depth_(n_),
first_(n_, -1),
parent_(n_, -1) {
assert(n_ > 0);
assert(0 <= root_ && root_ < n_);
/*
* Euler Tour
*
* tour[i] = {depth, vertex}
*
* 再帰 DFS を避けている。
*/
std::vector<rmq_value> tour;
tour.reserve(2 * n_ - 1);
struct frame {
int v;
int p;
int next;
};
std::vector<frame> stack;
stack.reserve(n_);
depth_[root_] = 0;
parent_[root_] = -1;
first_[root_] = 0;
tour.push_back({0, root_});
stack.push_back({root_, -1, 0});
while (!stack.empty()) {
frame& f = stack.back();
// v の全ての子を処理し終えた
if (f.next == (int)graph[f.v].size()) {
stack.pop_back();
// 親へ戻る
if (!stack.empty()) {
int p = stack.back().v;
tour.push_back({depth_[p], p});
}
continue;
}
int to = graph[f.v][f.next++].second;
if (to == f.p) continue;
parent_[to] = f.v;
depth_[to] = depth_[f.v] + graph[f.v][f.next-1].first;
first_[to] = (int)tour.size();
tour.push_back({depth_[to], to});
stack.push_back({to, f.v, 0});
}
rmq_ = dst_type(tour);
}
int size() const {
return n_;
}
int root() const {
return root_;
}
/*
* 根から v までの距離 = depth
*
* O(1)
*/
long long depth(int v) const {
assert(0 <= v && v < n_);
return depth_[v];
}
/*
* 元の木での親
*
* root なら -1
*
* O(1)
*/
int parent(int v) const {
assert(0 <= v && v < n_);
return parent_[v];
}
/*
* Lowest Common Ancestor
*
* O(1)
*/
int lca(int u, int v) const {
assert(0 <= u && u < n_);
assert(0 <= v && v < n_);
int l = first_[u];
int r = first_[v];
if (l > r) std::swap(l, r);
return rmq_.prod(l, r + 1).second;
}
/*
* 2頂点間の距離
*
* O(1)
*/
long long dist(int u, int v) const {
int w = lca(u, v);
return depth_[u]
+ depth_[v]
- 2 * depth_[w];
}
/*
* 与えられた頂点集合を含む Auxiliary Tree を構築する。
*
* https://smijake3.hatenablog.com/entry/2019/09/15/200200#%E3%82%BD%E3%83%BC%E3%83%882%E5%9B%9E%E3%81%AE%E6%96%B9%E6%B3%95
* の「ソート1回の方法」。
*
* k := distinct な入力頂点数
*
* 時間計算量:
* O(k log k)
*
* Auxiliary Tree の頂点数:
* <= 2k - 1
*
* 入力 vs はコピーして処理するので、呼び出し側の vector は変更しない。
*/
auxiliary_tree make_auxiliary_tree(
std::vector<int> vs
) const {
auxiliary_tree res;
if (vs.empty()) {
return res;
}
for (int v : vs) {
assert(0 <= v && v < n_);
}
/*
* preorder 順にソート。
*
* first_[v] は Euler Tour における最初の出現位置なので
* preorder 順序と一致する。
*/
std::sort(
vs.begin(),
vs.end(),
[&](int u, int v) {
return first_[u] < first_[v];
}
);
/*
* first_ は各頂点で異なるので、
* preorder 順でも同一頂点は隣接する。
*/
vs.erase(
std::unique(vs.begin(), vs.end()),
vs.end()
);
const int k = (int)vs.size();
/*
* stack:
* 現在処理している部分の祖先列。
*
* 全て元の木の頂点番号で管理する。
*/
std::vector<int> stack;
stack.reserve(2 * k);
/*
* Auxiliary Tree に出現した頂点。
*
* この時点ではソートされていない。
*/
std::vector<int> aux_vertices;
aux_vertices.reserve(2 * k);
/*
* Auxiliary Tree の有向辺
*
* {parent, child}
*
* いずれも元の木における頂点番号。
*/
std::vector<std::pair<int, int>> edges;
edges.reserve(2 * k);
stack.push_back(vs[0]);
aux_vertices.push_back(vs[0]);
/*
* 「ソート1回の方法」の本体。
*/
for (int i = 0; i + 1 < k; ++i) {
const int w = lca(vs[i], vs[i + 1]);
if (w != vs[i]) {
int last = stack.back();
stack.pop_back();
while (
!stack.empty()
&& depth_[w] < depth_[stack.back()]
) {
edges.emplace_back(
stack.back(),
last
);
last = stack.back();
stack.pop_back();
}
if (
stack.empty()
|| stack.back() != w
) {
stack.push_back(w);
aux_vertices.push_back(w);
edges.emplace_back(w, last);
} else {
edges.emplace_back(w, last);
}
}
stack.push_back(vs[i + 1]);
aux_vertices.push_back(vs[i + 1]);
}
/*
* stack に残っている辺を確定する。
*/
for (
int i = 0;
i + 1 < (int)stack.size();
++i
) {
edges.emplace_back(
stack[i],
stack[i + 1]
);
}
const int original_root = stack[0];
/*
* compressed_id を元の頂点番号の昇順に振る。
*
* これにより
*
* compressed_id(v)
*
* を lower_bound だけで求められる。
*/
std::sort(
aux_vertices.begin(),
aux_vertices.end()
);
aux_vertices.erase(
std::unique(
aux_vertices.begin(),
aux_vertices.end()
),
aux_vertices.end()
);
res.vertex = std::move(aux_vertices);
const int m = res.size();
res.graph.assign(m, {});
res.parent.assign(m, -1);
res.parent_edge_length.assign(m, 0);
res.is_terminal.assign(m, false);
/*
* Auxiliary Tree の頂点であることが分かっている場合の
* original -> compressed。
*
* compressed_id() と異なり存在チェックを省いている。
*/
auto id = [&](int v) -> int {
auto it =
std::lower_bound(
res.vertex.begin(),
res.vertex.end(),
v
);
assert(
it != res.vertex.end()
&& *it == v
);
return (int)(it - res.vertex.begin());
};
res.root = id(original_root);
/*
* 元々クエリで指定された頂点。
*/
for (int v : vs) {
res.is_terminal[id(v)] = true;
}
/*
* 辺を圧縮後の番号へ変換。
*/
for (auto [p, c] : edges) {
const int a = id(p);
const int b = id(c);
/*
* p は c の祖先なので、
* 元の木上の距離は depth の差で求まる。
*/
const long long length =
depth_[c] - depth_[p];
assert(length > 0);
res.graph[a].push_back({
b,
length
});
res.graph[b].push_back({
a,
length
});
res.parent[b] = a;
res.parent_edge_length[b] = length;
}
return res;
}
int n_;
int root_;
// 元の木における深さ
std::vector<long long> depth_;
// Euler Tour での最初の出現位置
//
// preorder の順序としても利用する。
std::vector<int> first_;
// 元の木における親
std::vector<int> parent_;
// Euler Tour 上の RMQ
dst_type rmq_;
};
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout<<fixed<<setprecision(10);
int n;
cin>>n;
vvi graph(n);
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
u--;v--;
graph[u].push_back(v);
graph[v].push_back(u);
}
tree_lca lca(graph);
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
a--;b--;
int c=lca.lca(a,b);
if(c==a){
cout<<"Alice"<<endl;
continue;
}
if(c==b){
cout<<"Bob"<<endl;
continue;
}
int d1=lca.dist(a,c),d2=lca.dist(b,c);
while(1){
if(d1<=d2){
cout<<"Alice"<<endl;
break;
}else{
int d=d1+d2;
d1-=d/2;
}
if(d2<=d1){
cout<<"Bob"<<endl;
break;
}else{
d2-=(d1+d2)/2;
}
}
}
}