結果

問題 No.3825 Jump
コンテスト
ユーザー Rho
提出日時 2026-11-10 15:58:21
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 782 ms / 2,000 ms
+ 773µs
コード長 3,083 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,240 ms
コンパイル使用メモリ 436,428 KB
実行使用メモリ 57,828 KB
最終ジャッジ日時 2026-11-22 12:40:59
合計ジャッジ時間 31,991 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge4_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
    1 | #pragma once
      |         ^~~~

ソースコード

diff #
raw source code

#pragma once
//# pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using ull=unsigned long long;
typedef pair<ll,ll> P;
#define vec vector
#define pb emplace_back
#define pcnt __builtin_popcountll
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rng(i,s,t) for(ll i=s;i<t;i++)
#define len(a) int((a).size())
#define all(a) a.begin(),a.end()
#define compress(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
constexpr ll INF=4e18;
constexpr ld EPS=1e-11;
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename itr> void printvec(itr begin, itr end) {
	for (itr p = begin; p < end; p++){
		if(p!=begin)cout<<" "; cout << *p;
	}
	cout << endl;
}
template <class T> T makevec(T value) {return value;}
template <class T, class... Args,
		std::enable_if_t<(sizeof...(Args) > 0), int> = 0>
auto makevec(std::size_t n, Args... args) {
	auto inner = makevec<T>(args...);
	return std::vector<decltype(inner)>(n, inner);
}

#include"atcoder/all"
using namespace atcoder;

struct S{
    long long val,idx;
};
S op(S x,S y){
    if(x.val>y.val)return y;
    return x;
}
S e() {
    return {LLONG_MAX,-1};
}

struct LCA{
    int N;
    vector<int>vs,depth,id,id_depth;
    vector<vector<ll>> G;
    segtree<S,op,e> seg;

    LCA(int n,vector<vector<ll>>&g){
        N=n;
        G=g;
        vs.resize(2*N-1);//DFSでの訪問順
        depth.resize(2*N-1);// 訪問順での根からの深さ
        id.resize(N); //id[i]:iが初めて現れるindex
        id_depth.resize(N);//頂点iの深さ
        seg=segtree<S,op,e>(2*N-1);
        int k=0;
        dfs(0,-1,0,k);
        rep(i,2*N-1){
            seg.set(i,{depth[i],i});
        }
    }

    int lca(int u,int v){
        return vs[seg.prod(min(id[u],id[v]),max(id[u],id[v])+1).idx];
    }

    void dfs(int now,int par,int d,int& k){
        id[now]=k;
        id_depth[now]=d;
        vs[k]=now;
        depth[k++]=d;
        for(auto e:G[now]){
            if(e==par)continue;
            dfs(e,now,d+1,k);
            vs[k]=now;
            depth[k++]=d;
        }
    }
};

int main(){
	ll n;
	cin>>n;
	vec<vec<ll>>graph(n);
	vec<ll>u(n),v(n);
	rep(i,n-1){
		cin>>u[i]>>v[i];
		u[i]--;
		v[i]--;
		graph[u[i]].push_back(v[i]);
		graph[v[i]].push_back(u[i]);
	}	
	LCA lca(n,graph);
	ll q;
	cin>>q;
	while(q--){
		ll a,b;
		cin>>a>>b;
		a--;
		b--;
		ll target=lca.lca(a,b);
		if(a==target){
			cout<<"Alice"<<endl;
		}
		else if(b==target){
			cout<<"Bob"<<endl;
		}
		else{
			//a---t---b
			ll l=0,r=lca.id_depth[a]+lca.id_depth[b]-2*lca.id_depth[target];
			ll mid=lca.id_depth[a]-lca.id_depth[target];
			ll cnt=0;
			while(l<mid&&mid<r){
				ll d=(r-l)/2;
				if(cnt%2==0){
					l+=d;
				}
				else{
					r-=d;
				}
				cnt++;
			}
			if(cnt%2==1)cout<<"Alice"<<endl;
			else cout<<"Bob"<<endl;
		}

	}	

}

/*
先にLCA(A,B) についた方が勝ち

*/
0