結果
| 問題 | No.3825 Jump |
| コンテスト | |
| ユーザー |
kidodesu
|
| 提出日時 | 2026-11-22 14:00:50 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
TLE
不安定
|
| 実行時間 | - |
| コード長 | 1,678 bytes |
| 記録 | |
| コンパイル時間 | 79 ms |
| コンパイル使用メモリ | 64,496 KB |
| 実行使用メモリ | 149,676 KB |
| 最終ジャッジ日時 | 2026-11-22 14:01:36 |
| 合計ジャッジ時間 | 44,496 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 TLE * 1 |
ソースコード
def main():
n = int(input())
node = [[] for _ in range(n)]
for _ in range(n-1):
u, v = list(map(lambda x: int(x)-1, input().split()))
node[u].append(v)
node[v].append(u)
D = [-1] * n
dub = [[-1]*30 for _ in range(n)]
D[0] = 0
S = [0]
while S:
u = S.pop()
for v in node[u]:
if D[v] == -1:
D[v] = D[u]+1
dub[v][0] = u
S.append(v)
for i in range(1, 30):
for u in range(n):
if dub[u][i-1] != -1:
dub[u][i] = dub[dub[u][i-1]][i-1]
def LCA(u, v):
if D[u] > D[v]:
u, v = v, u
k = D[v] - D[u]
i = 0
while k:
if k & 1:
v = dub[v][i]
k >>= 1
i += 1
if u == v:
return u
for i in range(29, -1, -1):
if dub[u][i] != dub[v][i]:
u, v = dub[u][i], dub[v][i]
return dub[u][0]
for _ in range(int(input())):
a, b = list(map(lambda x: int(x)-1, input().split()))
c = LCA(a, b)
d0 = D[a]-D[c]
d1 = D[b]-D[c]
t = 0
if d0 == d1 == 0:
print("Alice")
while d0 or d1:
if t == 0:
le = (d0+d1)//2
if d0 <= le:
print("Alice")
d0 = d1 = 0
else:
d0 -= le
else:
le = (d0+d1)//2
if d1 <= le:
print("Bob")
d0 = d1 = 0
else:
d1 -= le
t ^= 1
main()
kidodesu