結果

問題 No.2800 Game on Tree Inverse
ユーザー chineristACchineristAC
提出日時 2024-06-28 21:29:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,851 ms / 4,000 ms
コード長 3,868 bytes
コンパイル時間 208 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 470,700 KB
最終ジャッジ日時 2024-06-28 21:31:20
合計ジャッジ時間 96,047 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 52 ms
55,680 KB
testcase_01 AC 52 ms
56,320 KB
testcase_02 AC 52 ms
55,808 KB
testcase_03 AC 2,220 ms
314,988 KB
testcase_04 AC 2,431 ms
370,752 KB
testcase_05 AC 2,390 ms
367,852 KB
testcase_06 AC 2,484 ms
402,720 KB
testcase_07 AC 2,598 ms
468,740 KB
testcase_08 AC 2,580 ms
470,700 KB
testcase_09 AC 2,383 ms
470,104 KB
testcase_10 AC 2,273 ms
309,772 KB
testcase_11 AC 2,084 ms
312,668 KB
testcase_12 AC 2,113 ms
319,652 KB
testcase_13 AC 2,467 ms
384,756 KB
testcase_14 AC 2,387 ms
381,824 KB
testcase_15 AC 2,183 ms
311,276 KB
testcase_16 AC 2,418 ms
381,260 KB
testcase_17 AC 2,195 ms
326,248 KB
testcase_18 AC 2,851 ms
382,864 KB
testcase_19 AC 2,510 ms
406,068 KB
testcase_20 AC 2,325 ms
318,600 KB
testcase_21 AC 2,594 ms
380,552 KB
testcase_22 AC 2,441 ms
399,036 KB
testcase_23 AC 2,182 ms
314,024 KB
testcase_24 AC 2,243 ms
353,816 KB
testcase_25 AC 2,387 ms
377,828 KB
testcase_26 AC 2,212 ms
341,896 KB
testcase_27 AC 2,294 ms
374,144 KB
testcase_28 AC 2,375 ms
374,160 KB
testcase_29 AC 2,268 ms
307,308 KB
testcase_30 AC 2,412 ms
366,384 KB
testcase_31 AC 2,081 ms
349,672 KB
testcase_32 AC 2,110 ms
310,524 KB
testcase_33 AC 2,208 ms
311,516 KB
testcase_34 AC 2,040 ms
364,136 KB
testcase_35 AC 2,210 ms
328,644 KB
testcase_36 AC 58 ms
64,972 KB
testcase_37 AC 64 ms
65,152 KB
testcase_38 AC 65 ms
64,000 KB
testcase_39 AC 60 ms
62,464 KB
testcase_40 AC 63 ms
56,320 KB
testcase_41 AC 52 ms
56,064 KB
testcase_42 AC 63 ms
64,640 KB
testcase_43 AC 64 ms
65,024 KB
testcase_44 AC 65 ms
65,152 KB
testcase_45 AC 61 ms
63,488 KB
testcase_46 AC 86 ms
67,456 KB
testcase_47 AC 159 ms
81,664 KB
testcase_48 AC 148 ms
81,152 KB
testcase_49 AC 234 ms
92,244 KB
testcase_50 AC 225 ms
84,904 KB
testcase_51 AC 1,214 ms
291,096 KB
testcase_52 AC 221 ms
93,996 KB
testcase_53 AC 391 ms
135,680 KB
testcase_54 AC 1,220 ms
290,492 KB
testcase_55 AC 1,789 ms
301,540 KB
testcase_56 AC 1,474 ms
292,800 KB
testcase_57 AC 2,086 ms
305,516 KB
testcase_58 AC 809 ms
238,536 KB
testcase_59 AC 1,012 ms
286,632 KB
testcase_60 AC 755 ms
223,652 KB
testcase_61 AC 534 ms
180,540 KB
testcase_62 AC 808 ms
230,528 KB
testcase_63 AC 797 ms
250,956 KB
testcase_64 AC 420 ms
145,448 KB
testcase_65 AC 420 ms
144,640 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)
        BT[v] = None
    
    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)
0