結果
問題 | No.1424 Ultrapalindrome |
ユーザー | kuro_B |
提出日時 | 2023-04-06 14:40:15 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,478 bytes |
コンパイル時間 | 446 ms |
コンパイル使用メモリ | 82,448 KB |
実行使用メモリ | 270,064 KB |
最終ジャッジ日時 | 2024-04-10 11:43:48 |
合計ジャッジ時間 | 10,833 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 131 ms
83,024 KB |
testcase_01 | AC | 129 ms
83,292 KB |
testcase_02 | AC | 128 ms
83,228 KB |
testcase_03 | AC | 130 ms
83,188 KB |
testcase_04 | AC | 130 ms
83,204 KB |
testcase_05 | WA | - |
testcase_06 | AC | 127 ms
83,344 KB |
testcase_07 | AC | 127 ms
82,756 KB |
testcase_08 | WA | - |
testcase_09 | AC | 425 ms
108,108 KB |
testcase_10 | AC | 438 ms
107,680 KB |
testcase_11 | AC | 306 ms
102,120 KB |
testcase_12 | AC | 352 ms
105,988 KB |
testcase_13 | AC | 242 ms
94,876 KB |
testcase_14 | AC | 364 ms
104,520 KB |
testcase_15 | AC | 145 ms
88,976 KB |
testcase_16 | WA | - |
testcase_17 | AC | 313 ms
103,936 KB |
testcase_18 | AC | 285 ms
99,268 KB |
testcase_19 | AC | 384 ms
104,184 KB |
testcase_20 | AC | 252 ms
93,228 KB |
testcase_21 | AC | 412 ms
110,040 KB |
testcase_22 | AC | 293 ms
97,320 KB |
testcase_23 | AC | 171 ms
90,360 KB |
testcase_24 | AC | 250 ms
95,232 KB |
testcase_25 | AC | 242 ms
93,532 KB |
testcase_26 | AC | 417 ms
105,568 KB |
testcase_27 | WA | - |
testcase_28 | AC | 512 ms
233,768 KB |
testcase_29 | WA | - |
testcase_30 | AC | 255 ms
112,912 KB |
testcase_31 | WA | - |
ソースコード
###スニペット始まり### 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 def dfs(s, dist): dists[s]=dist for v in graph[s]: if dists[v]==-1: dfs(v, dist+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: leaf_cnt=0 if dists.count(diam)==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 for v in graph[s]: if not visited[v]: flag=False dfs3(v, dist+1) if flag: dist_set.add(dist) dfs3(center,0) if len(dist_set)==1: print('Yes') else: print('No')