結果
問題 | No.1424 Ultrapalindrome |
ユーザー | kuro_B |
提出日時 | 2023-04-06 14:46:44 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,591 bytes |
コンパイル時間 | 513 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 271,612 KB |
最終ジャッジ日時 | 2024-04-10 11:47:27 |
合計ジャッジ時間 | 9,564 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 116 ms
83,008 KB |
testcase_01 | AC | 113 ms
82,804 KB |
testcase_02 | AC | 112 ms
83,196 KB |
testcase_03 | AC | 116 ms
83,056 KB |
testcase_04 | AC | 114 ms
82,804 KB |
testcase_05 | AC | 112 ms
83,136 KB |
testcase_06 | AC | 112 ms
83,140 KB |
testcase_07 | AC | 113 ms
83,228 KB |
testcase_08 | AC | 114 ms
83,112 KB |
testcase_09 | AC | 298 ms
107,924 KB |
testcase_10 | AC | 314 ms
107,940 KB |
testcase_11 | AC | 261 ms
101,632 KB |
testcase_12 | AC | 283 ms
106,820 KB |
testcase_13 | AC | 190 ms
94,016 KB |
testcase_14 | AC | 262 ms
104,368 KB |
testcase_15 | AC | 126 ms
88,676 KB |
testcase_16 | WA | - |
testcase_17 | AC | 257 ms
104,040 KB |
testcase_18 | AC | 237 ms
99,436 KB |
testcase_19 | AC | 328 ms
104,412 KB |
testcase_20 | AC | 219 ms
93,188 KB |
testcase_21 | AC | 342 ms
110,216 KB |
testcase_22 | AC | 258 ms
97,232 KB |
testcase_23 | AC | 148 ms
90,556 KB |
testcase_24 | AC | 213 ms
95,160 KB |
testcase_25 | AC | 209 ms
93,472 KB |
testcase_26 | AC | 338 ms
105,564 KB |
testcase_27 | AC | 326 ms
112,472 KB |
testcase_28 | AC | 465 ms
234,052 KB |
testcase_29 | AC | 659 ms
271,612 KB |
testcase_30 | AC | 233 ms
113,120 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 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')