結果
問題 | No.363 門松サイクル |
ユーザー | maspy |
提出日時 | 2020-05-16 16:12:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 764 ms / 4,000 ms |
コード長 | 2,443 bytes |
コンパイル時間 | 268 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 140,276 KB |
最終ジャッジ日時 | 2024-09-22 11:49:10 |
合計ジャッジ時間 | 13,360 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
53,608 KB |
testcase_01 | AC | 39 ms
53,176 KB |
testcase_02 | AC | 87 ms
76,964 KB |
testcase_03 | AC | 72 ms
74,448 KB |
testcase_04 | AC | 90 ms
77,036 KB |
testcase_05 | AC | 87 ms
77,300 KB |
testcase_06 | AC | 99 ms
77,068 KB |
testcase_07 | AC | 91 ms
76,888 KB |
testcase_08 | AC | 104 ms
76,932 KB |
testcase_09 | AC | 282 ms
96,092 KB |
testcase_10 | AC | 372 ms
98,008 KB |
testcase_11 | AC | 435 ms
128,112 KB |
testcase_12 | AC | 538 ms
132,456 KB |
testcase_13 | AC | 640 ms
133,204 KB |
testcase_14 | AC | 652 ms
132,296 KB |
testcase_15 | AC | 409 ms
124,616 KB |
testcase_16 | AC | 284 ms
102,904 KB |
testcase_17 | AC | 375 ms
140,276 KB |
testcase_18 | AC | 684 ms
119,408 KB |
testcase_19 | AC | 764 ms
119,852 KB |
testcase_20 | AC | 728 ms
125,060 KB |
testcase_21 | AC | 426 ms
118,404 KB |
testcase_22 | AC | 440 ms
123,420 KB |
testcase_23 | AC | 380 ms
131,276 KB |
testcase_24 | AC | 37 ms
52,812 KB |
testcase_25 | AC | 37 ms
53,304 KB |
testcase_26 | AC | 285 ms
139,300 KB |
testcase_27 | AC | 262 ms
139,292 KB |
testcase_28 | AC | 504 ms
139,548 KB |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines N = int(readline()) A = (0, ) + tuple(map(int, readline().split())) G = [[] for _ in range(N + 1)] for _ in range(N - 1): x, y = map(int, readline().split()) G[x].append(y) G[y].append(x) Q = int(readline()) m = map(int, read().split()) query = tuple(zip(m, m)) parent = [0] * (N + 1) depth = [0] * (N + 1) stack = [] order = [] root = 1 stack = [root] while stack: v = stack.pop() order.append(v) for w in G[v]: if w == parent[v]: continue parent[w] = v depth[w] = depth[v] + 1 stack.append(w) K = 18 P = [parent] for _ in range(K): p = P[-1] P.append([p[v] for v in p]) def LCA(u, v): du, dv = depth[u], depth[v] if du < dv: du, dv = dv, du u, v = v, u n = du - dv for i in range(K): if n & 1: u = P[i][u] n >>= 1 if u == v: return u for i in range(K - 1, -1, -1): u1, v1 = P[i][u], P[i][v] if u1 == v1: continue u, v = u1, v1 return parent[u] def is_kadomatsu(a, b, c): if a == c: return False return (a > b < c) or (a < b > c) longest_kadomatsu = [0] * (N + 1) for v in order[1:]: p = parent[v] pp = parent[p] if not p: longest_kadomatsu[v] = 0 elif not pp: longest_kadomatsu[v] = 1 else: a, b, c = A[v], A[p], A[pp] if is_kadomatsu(a, b, c): longest_kadomatsu[v] = longest_kadomatsu[p] + 1 else: longest_kadomatsu[v] = 1 def ascend(v, k): for i in range(K): if k & 1: v = P[i][v] k >>= 1 return v longest_kadomatsu def solve(u,v): w = LCA(u,v) if v == w: u,v = v,u du, dv, dw = depth[u], depth[v], depth[w] if longest_kadomatsu[v] < dv - dw: return False if longest_kadomatsu[u] < du - dw: return False if u == w: v1 = parent[v] v2 = ascend(v, dv-dw-1) return is_kadomatsu(A[v2], A[w], A[v]) and is_kadomatsu(A[w], A[v], A[v1]) v1 = parent[v] v2 = ascend(v, dv-dw-1) u1 = parent[u] u2 = ascend(u, du-dw-1) return is_kadomatsu(A[v2], A[w], A[u2]) and is_kadomatsu(A[v], A[u], A[u1]) and is_kadomatsu(A[u], A[v], A[v1]) query for a,b in query: print('YES' if solve(a,b) else 'NO')