結果
| 問題 | No.3825 Jump |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-14 19:30:12 |
| 言語 | Python3 (3.15.2 + numpy 2.5.4 + scipy 1.18.1 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 2,274 bytes |
| 記録 | |
| コンパイル時間 | 53 ms |
| コンパイル使用メモリ | 14,848 KB |
| 実行使用メモリ | 115,456 KB |
| 最終ジャッジ日時 | 2026-11-22 12:42:26 |
| 合計ジャッジ時間 | 47,704 ms |
|
ジャッジサーバーID (参考情報) |
judge6_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 TLE * 3 |
ソースコード
import sys
# このコードは、zeta7532 が人力で書いた C++ コードを
# できるだけそのまま Python に言語変換したものです。
sys.setrecursionlimit(1 << 25)
input = sys.stdin.buffer.readline
MOD = 998244353
class LCA:
def __init__(self, G, root=0):
self.init(G, root)
def init(self, G, root=0):
v = len(G)
k = 1
while (1 << k) < v:
k += 1
self.par = [[-1] * v for _ in range(k)]
self.dis = [-1] * v
self.dfs(G, root, -1, 0)
for i in range(k - 1):
for j in range(v):
if self.par[i][j] < 0:
self.par[i + 1][j] = -1
else:
self.par[i + 1][j] = self.par[i][self.par[i][j]]
def dfs(self, G, v, p, d):
self.par[0][v] = p
self.dis[v] = d
for nv in G[v]:
if nv != p:
self.dfs(G, nv, v, d + 1)
def query(self, u, v):
if self.dis[u] < self.dis[v]:
u, v = v, u
K = len(self.par)
for k in range(K):
if ((self.dis[u] - self.dis[v]) >> k) & 1:
u = self.par[k][u]
if u == v:
return u
for k in range(K - 1, -1, -1):
if self.par[k][u] != self.par[k][v]:
u = self.par[k][u]
v = self.par[k][v]
return self.par[0][u]
def get_dis(self, u, v):
return self.dis[u] + self.dis[v] - 2 * self.dis[self.query(u, v)]
def f(x, y):
if x <= y:
return 1
return 1 - f(y, (x - y + 1) // 2)
def main():
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
G[u].append(v)
G[v].append(u)
lca = LCA(G)
Q = int(input())
output = []
for _ in range(Q):
a, b = map(int, input().split())
a -= 1
b -= 1
q = lca.query(a, b)
dis_a = lca.dis[a] - lca.dis[q]
dis_b = lca.dis[b] - lca.dis[q]
ans = f(dis_a, dis_b)
if ans:
output.append("Alice")
else:
output.append("Bob")
print("\n".join(output))
if __name__ == "__main__":
main()