結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
|
提出日時 | 2023-02-24 02:02:13 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 736 ms / 2,000 ms |
コード長 | 1,617 bytes |
コンパイル時間 | 86 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 35,608 KB |
最終ジャッジ日時 | 2024-07-23 18:26:13 |
合計ジャッジ時間 | 11,554 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#!/usr/bin/env python3from bisect import bisect_left, bisect_rightfrom collections import dequefrom itertools import permutationsfrom sys import setrecursionlimitdpos4 = ((1, 0), (0, 1), (-1, 0), (0, -1))dpos8 = ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1))mod1 = 10**9 + 7mod2 = 998244353inf = 1 << 60def main():N = int(input())edges = [[] for _ in range(N)]for _ in range(N - 1):u, v = map(int, input().split())u -= 1v -= 1edges[u].append(v)edges[v].append(u)dp1 = [True] * Ndp2 = [True] * Nsetrecursionlimit(10**6)def dfs1(fr, prev=-1):val = Falsefor to in edges[fr]:if to == prev:continuedfs1(to, fr)val |= dp1[to]dp1[fr] = not valdef dfs2(fr, prev=-1):val = Falsefor to in edges[fr]:val |= dp1[to]dp2[fr] = not valL = len(edges[fr])lval = [False] * (L + 1)rval = [False] * (L + 1)for i in range(L):to = edges[fr][i]lval[i + 1] = lval[i] or dp1[to]j = L - 1 - ito = edges[fr][j]rval[j] = rval[j + 1] or dp1[to]for i in range(L):to = edges[fr][i]if to == prev:continuedp1[fr] = not (lval[i] or rval[i + 1])dfs2(to, fr)dfs1(0)dfs2(0)print(sum(dp2))if sum(dp2):print(*(i + 1 for i in range(N) if dp2[i]), sep='\n')if __name__ == "__main__":main()