結果
問題 | No.1424 Ultrapalindrome |
ユーザー | kuro_B |
提出日時 | 2023-04-06 14:50:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 731 ms / 2,000 ms |
コード長 | 2,675 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 277,948 KB |
最終ジャッジ日時 | 2024-04-10 11:49:52 |
合計ジャッジ時間 | 10,260 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 128 ms
83,188 KB |
testcase_01 | AC | 129 ms
83,204 KB |
testcase_02 | AC | 127 ms
83,224 KB |
testcase_03 | AC | 127 ms
83,300 KB |
testcase_04 | AC | 128 ms
82,788 KB |
testcase_05 | AC | 125 ms
82,824 KB |
testcase_06 | AC | 127 ms
83,356 KB |
testcase_07 | AC | 125 ms
83,344 KB |
testcase_08 | AC | 127 ms
83,212 KB |
testcase_09 | AC | 360 ms
108,228 KB |
testcase_10 | AC | 379 ms
107,168 KB |
testcase_11 | AC | 305 ms
102,340 KB |
testcase_12 | AC | 352 ms
106,312 KB |
testcase_13 | AC | 220 ms
94,284 KB |
testcase_14 | AC | 313 ms
104,512 KB |
testcase_15 | AC | 144 ms
89,120 KB |
testcase_16 | AC | 290 ms
101,840 KB |
testcase_17 | AC | 309 ms
103,776 KB |
testcase_18 | AC | 278 ms
98,884 KB |
testcase_19 | AC | 401 ms
104,224 KB |
testcase_20 | AC | 247 ms
93,316 KB |
testcase_21 | AC | 427 ms
113,128 KB |
testcase_22 | AC | 293 ms
97,640 KB |
testcase_23 | AC | 168 ms
90,152 KB |
testcase_24 | AC | 247 ms
94,960 KB |
testcase_25 | AC | 239 ms
93,424 KB |
testcase_26 | AC | 415 ms
106,040 KB |
testcase_27 | AC | 391 ms
112,220 KB |
testcase_28 | AC | 527 ms
240,568 KB |
testcase_29 | AC | 731 ms
277,948 KB |
testcase_30 | AC | 257 ms
111,864 KB |
testcase_31 | AC | 240 ms
111,880 KB |
ソースコード
###スニペット始まり### import sys, re from copy import copy, deepcopy from math import ceil, floor, sqrt,factorial, gcd, pi, degrees, radians, sin, asin, cos, acos, tan, atan2 from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import permutations, accumulate, product, combinations, combinations_with_replacement from bisect import bisect, bisect_left, bisect_right from functools import reduce, lru_cache from string import ascii_uppercase, ascii_lowercase from decimal import Decimal, ROUND_HALF_UP #四捨五入用 def input(): return sys.stdin.readline().rstrip('\n') #easy-testのpypyでは再帰数を下げる。 if __file__=='prog.py': sys.setrecursionlimit(10**5) else: sys.setrecursionlimit(10**6) def lcm(a, b): return a * b // gcd(a, b) #3つ以上の最大公約数/最小公倍数 def gcd_v2(l: list): return reduce(gcd, l) def lcm_v2(l: list): return reduce(lcm, l) #nPk def nPk(n, k): return factorial(n) // factorial(n - k) #逆元 def modinv(a, mod=10**9+7): return pow(a, mod-2, mod) INF = float('inf') MOD = 10 ** 9 + 7 ###スニペット終わり### N=int(input()) graph = [[] for _ in range(N)] for _ in range(N-1): a, b = map(int, input().split()) graph[a-1].append(b-1) graph[b-1].append(a-1) # 有向グラフなら消す dists=[-1]*N leaf_cnt=0 def dfs(s, dist): global leaf_cnt dists[s]=dist flag=True for v in graph[s]: if dists[v]==-1: flag=False dfs(v, dist+1) if flag: leaf_cnt+=1 dfs(0,0) s=dists.index(max(dists)) #0から一番遠い点を求める。 dists=[-1]*N prev=defaultdict(int) def dfs2(s, dist): dists[s]=dist for v in graph[s]: if dists[v]==-1: dfs2(v, dist+1) prev[v]=s dfs2(s,0) diam=max(dists) #直径 diam_leaf=dists.index(diam) #直径の末端。 if diam%2!=0: if leaf_cnt==1: #もし、葉がひとつならYes print('Yes') else: print('No') else: #直径が偶数なら可能性あり。 #まずは中心を求める。 center=diam_leaf for _ in range(diam//2): center=prev[center] dist_set=set() visited=[False]*N def dfs3(s, dist): visited[s]=True flag=True cnt=0 for v in graph[s]: if not visited[v]: cnt+=1 flag=False dfs3(v, dist+1) if s!=center and cnt>=2: print('No') exit() if flag: dist_set.add(dist) dfs3(center,0) if len(dist_set)==1: print('Yes') else: print('No')