結果
問題 | No.1153 ねこちゃんゲーム |
ユーザー |
![]() |
提出日時 | 2020-06-29 02:50:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 850 ms / 2,500 ms |
コード長 | 1,390 bytes |
コンパイル時間 | 387 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 138,412 KB |
最終ジャッジ日時 | 2024-09-14 08:48:24 |
合計ジャッジ時間 | 37,939 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 40 |
ソースコード
from collections import deque import sys input = lambda: sys.stdin.readline().rstrip() N, M = map(int, input().split()) A = [int(a) - 1 for a in input().split()] X = [[] for i in range(N)] for _ in range(N - 1): x, y = map(int, input().split()) X[x-1].append(y-1) X[y-1].append(x-1) P = [-1] * N Q = deque([0]) R = [] while Q: i = deque.popleft(Q) R.append(i) for a in X[i]: if a != P[i]: P[a] = i X[a].remove(i) deque.append(Q, a) G = [0] * N # Grundy Number L = [[] for _ in range(N)] for i in R[::-1]: m = min(len(X[i]) + 2, 20) L[i] = [0] * m for j in X[i]: if G[j] < m: L[i][G[j]] += 1 for k in range(m): if not L[i][k]: G[i] = k break G_bu = G[:] for i in R[1:]: m = min(len(X[i]) + 2, 20) g = G[i] p = P[i] pg = G[p] if g < pg and L[p][g] == 1: pg = g if pg < m: L[i][pg] += 1 if pg == g: for k in range(g, m): if not L[i][k]: G[i] = k break s = 0 for a in A: s ^= G[a] if s == 0: print(-1, -1) else: for i, a in enumerate(A): if G[a] ^ s < G[a]: for b in X[a]: if G[a] ^ s == G_bu[b]: print(i+1, b+1) exit() print(i+1, P[a] + 1) exit()