結果
| 問題 | No.2800 Game on Tree Inverse |
| ユーザー |
 chineristAC
|
| 提出日時 | 2024-06-28 21:28:46 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 3,926 bytes |
| コンパイル時間 | 139 ms |
| コンパイル使用メモリ | 82,248 KB |
| 実行使用メモリ | 528,872 KB |
| 最終ジャッジ日時 | 2024-06-28 21:30:49 |
| 合計ジャッジ時間 | 110,715 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 37 ms
58,048 KB |
| testcase_01 | AC | 40 ms
56,660 KB |
| testcase_02 | AC | 39 ms
56,840 KB |
| testcase_03 | MLE | - |
| testcase_04 | AC | 2,827 ms
478,792 KB |
| testcase_05 | AC | 2,546 ms
474,212 KB |
| testcase_06 | AC | 2,618 ms
475,932 KB |
| testcase_07 | AC | 2,602 ms
472,064 KB |
| testcase_08 | AC | 2,550 ms
470,704 KB |
| testcase_09 | AC | 2,331 ms
470,140 KB |
| testcase_10 | MLE | - |
| testcase_11 | AC | 2,686 ms
501,988 KB |
| testcase_12 | MLE | - |
| testcase_13 | AC | 2,842 ms
505,192 KB |
| testcase_14 | AC | 2,905 ms
501,244 KB |
| testcase_15 | MLE | - |
| testcase_16 | AC | 2,736 ms
498,244 KB |
| testcase_17 | MLE | - |
| testcase_18 | AC | 2,911 ms
506,776 KB |
| testcase_19 | AC | 2,646 ms
478,764 KB |
| testcase_20 | MLE | - |
| testcase_21 | AC | 2,910 ms
508,036 KB |
| testcase_22 | AC | 2,612 ms
477,616 KB |
| testcase_23 | AC | 2,612 ms
506,948 KB |
| testcase_24 | AC | 2,889 ms
491,680 KB |
| testcase_25 | AC | 2,698 ms
479,436 KB |
| testcase_26 | AC | 2,793 ms
475,680 KB |
| testcase_27 | AC | 2,512 ms
497,912 KB |
| testcase_28 | AC | 2,556 ms
474,536 KB |
| testcase_29 | MLE | - |
| testcase_30 | AC | 2,844 ms
500,948 KB |
| testcase_31 | AC | 2,740 ms
494,456 KB |
| testcase_32 | AC | 2,717 ms
502,840 KB |
| testcase_33 | AC | 2,747 ms
497,488 KB |
| testcase_34 | AC | 2,487 ms
492,180 KB |
| testcase_35 | MLE | - |
| testcase_36 | AC | 51 ms
65,508 KB |
| testcase_37 | AC | 50 ms
66,360 KB |
| testcase_38 | AC | 48 ms
64,092 KB |
| testcase_39 | AC | 44 ms
64,552 KB |
| testcase_40 | AC | 41 ms
58,072 KB |
| testcase_41 | AC | 40 ms
56,924 KB |
| testcase_42 | AC | 49 ms
64,584 KB |
| testcase_43 | AC | 50 ms
65,292 KB |
| testcase_44 | AC | 51 ms
65,788 KB |
| testcase_45 | AC | 51 ms
64,324 KB |
| testcase_46 | AC | 61 ms
68,796 KB |
| testcase_47 | AC | 134 ms
81,784 KB |
| testcase_48 | AC | 125 ms
81,416 KB |
| testcase_49 | AC | 199 ms
94,084 KB |
| testcase_50 | AC | 172 ms
86,908 KB |
| testcase_51 | AC | 1,282 ms
323,492 KB |
| testcase_52 | AC | 205 ms
95,352 KB |
| testcase_53 | AC | 332 ms
135,672 KB |
| testcase_54 | AC | 1,238 ms
319,396 KB |
| testcase_55 | AC | 2,523 ms
462,192 KB |
| testcase_56 | AC | 1,929 ms
387,944 KB |
| testcase_57 | AC | 2,762 ms
501,448 KB |
| testcase_58 | AC | 686 ms
239,176 KB |
| testcase_59 | AC | 1,095 ms
287,812 KB |
| testcase_60 | AC | 644 ms
224,172 KB |
| testcase_61 | AC | 444 ms
181,028 KB |
| testcase_62 | AC | 628 ms
231,524 KB |
| testcase_63 | AC | 701 ms
250,816 KB |
| testcase_64 | AC | 332 ms
145,948 KB |
| testcase_65 | AC | 341 ms
145,476 KB |
ソースコード
"""
出力含めてまったく同じ問題作問しててびっくり！
"""
class BinaryTrie:
class node:
def __init__(self):
self.left = None
self.right = None
self.cnt = 0
def __init__(self,n):
self.root = self.node()
self.n = n
self.xor = 0
self.set = set()
def __len__(self):
return self.root.cnt
def __str__(self):
res = []
for val in self.set:
res.append(val^self.xor)
res.sort()
res = ["["] + [str(val)+", " for val in res] + ["]"]
return "".join(res)
def append(self,x):
x ^= self.xor
if x in self.set:
return
self.set.add(x)
pos = self.root
for i in range(self.n-1,-1,-1):
pos.cnt += 1
if x>>i & 1:
if pos.right is None:
pos.right = self.node()
pos = pos.right
else:
if pos.left is None:
pos.left = self.node()
pos = pos.left
pos.cnt = 1
def all_prod(self,x):
self.xor ^= x
def mex(self):
res = 0
pos = self.root
t = 1<<self.n
for i in range(self.n-1,-1,-1):
t >>= 1
if self.xor>>i & 1:
check = 0
if pos.right:
check = pos.right.cnt
if check==t:
res += t
if not pos.left:
return res
else:
pos = pos.left
else:
if not pos.right:
return res
else:
pos = pos.right
else:
check = 0
if pos.left:
check = pos.left.cnt
if check==t:
res += t
if not pos.right:
return res
else:
pos = pos.right
else:
if not pos.left:
return res
else:
pos = pos.left
return res
import sys,random
from collections import deque
input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())
def solve(N,edge):
parent = [-1] * N
deq = deque([0])
topo = []
while deq:
v = deq.popleft()
topo.append(v)
for nv in edge[v]:
if nv == parent[v]:
continue
parent[nv] = v
deq.append(nv)
grundy = [-1 for v in range(N)]
BT = [BinaryTrie(17) for i in range(N)]
def merge(v,pv):
if len(BT[v]) > len(BT[pv]):
BT[v],BT[pv] = BT[pv],BT[v]
x = BT[v].xor
for val in BT[v].set:
BT[pv].append(x^val)
for v in topo[::-1]:
BT[v].append(0)
G = 0
for nv in edge[v]:
if nv == parent[v]:
continue
G ^= grundy[nv]
BT[nv].all_prod(grundy[nv])
merge(nv,v)
BT[v].all_prod(G)
grundy[v] = BT[v].mex()
CG = [0 for v in range(N)]
for v in range(N):
for nv in edge[v]:
if parent[v]==nv:
continue
CG[v] ^= grundy[nv]
res = []
tmp = [0 for v in range(N)]
for v in topo:
if CG[v]^tmp[v]==0:
res.append(v+1)
for nv in edge[v]:
tmp[nv] = tmp[v]^CG[v]^grundy[nv]
return sorted(res)
N = int(input())
edge = [[] for v in range(N)]
for i in range(N-1):
u,v = mi()
edge[u-1].append(v-1)
edge[v-1].append(u-1)
res = solve(N,edge)
print("Alice")
print(len(res))
print(*res)