結果
問題 | No.2822 Lights Up! (Tree Edition) |
ユーザー |
![]() |
提出日時 | 2024-07-27 02:38:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 682 ms / 2,000 ms |
コード長 | 4,019 bytes |
コンパイル時間 | 528 ms |
コンパイル使用メモリ | 82,136 KB |
実行使用メモリ | 167,516 KB |
最終ジャッジ日時 | 2024-07-27 02:39:05 |
合計ジャッジ時間 | 25,660 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
53,368 KB |
testcase_01 | AC | 40 ms
54,448 KB |
testcase_02 | AC | 666 ms
160,668 KB |
testcase_03 | AC | 570 ms
159,844 KB |
testcase_04 | AC | 599 ms
160,648 KB |
testcase_05 | AC | 682 ms
158,928 KB |
testcase_06 | AC | 559 ms
167,516 KB |
testcase_07 | AC | 597 ms
158,684 KB |
testcase_08 | AC | 332 ms
114,680 KB |
testcase_09 | AC | 568 ms
154,876 KB |
testcase_10 | AC | 483 ms
134,612 KB |
testcase_11 | AC | 381 ms
125,056 KB |
testcase_12 | AC | 427 ms
123,488 KB |
testcase_13 | AC | 404 ms
107,180 KB |
testcase_14 | AC | 494 ms
128,060 KB |
testcase_15 | AC | 437 ms
124,672 KB |
testcase_16 | AC | 125 ms
78,648 KB |
testcase_17 | AC | 164 ms
80,600 KB |
testcase_18 | AC | 193 ms
84,552 KB |
testcase_19 | AC | 153 ms
80,704 KB |
testcase_20 | AC | 184 ms
81,152 KB |
testcase_21 | AC | 194 ms
84,216 KB |
testcase_22 | AC | 170 ms
84,820 KB |
testcase_23 | AC | 181 ms
82,508 KB |
testcase_24 | AC | 167 ms
83,772 KB |
testcase_25 | AC | 150 ms
80,668 KB |
testcase_26 | AC | 188 ms
82,940 KB |
testcase_27 | AC | 107 ms
77,368 KB |
testcase_28 | AC | 246 ms
83,660 KB |
testcase_29 | AC | 246 ms
86,740 KB |
testcase_30 | AC | 190 ms
83,176 KB |
testcase_31 | AC | 170 ms
80,668 KB |
testcase_32 | AC | 219 ms
86,720 KB |
testcase_33 | AC | 194 ms
86,524 KB |
testcase_34 | AC | 187 ms
86,864 KB |
testcase_35 | AC | 188 ms
86,988 KB |
testcase_36 | AC | 192 ms
86,932 KB |
testcase_37 | AC | 176 ms
86,844 KB |
testcase_38 | AC | 213 ms
86,916 KB |
testcase_39 | AC | 184 ms
86,512 KB |
testcase_40 | AC | 201 ms
87,012 KB |
testcase_41 | AC | 194 ms
86,532 KB |
testcase_42 | AC | 189 ms
86,884 KB |
testcase_43 | AC | 199 ms
86,828 KB |
testcase_44 | AC | 223 ms
86,944 KB |
testcase_45 | AC | 214 ms
85,792 KB |
testcase_46 | AC | 190 ms
86,772 KB |
testcase_47 | AC | 222 ms
86,488 KB |
testcase_48 | AC | 105 ms
77,788 KB |
testcase_49 | AC | 113 ms
77,868 KB |
testcase_50 | AC | 117 ms
77,756 KB |
testcase_51 | AC | 117 ms
77,644 KB |
testcase_52 | AC | 113 ms
77,804 KB |
testcase_53 | AC | 110 ms
77,792 KB |
testcase_54 | AC | 107 ms
77,728 KB |
testcase_55 | AC | 118 ms
77,924 KB |
testcase_56 | AC | 116 ms
77,632 KB |
testcase_57 | AC | 110 ms
77,684 KB |
testcase_58 | AC | 112 ms
77,728 KB |
testcase_59 | AC | 108 ms
77,828 KB |
testcase_60 | AC | 135 ms
77,784 KB |
testcase_61 | AC | 110 ms
77,648 KB |
testcase_62 | AC | 107 ms
77,912 KB |
testcase_63 | AC | 116 ms
77,864 KB |
testcase_64 | AC | 114 ms
77,992 KB |
testcase_65 | AC | 117 ms
77,600 KB |
testcase_66 | AC | 110 ms
77,700 KB |
testcase_67 | AC | 122 ms
77,956 KB |
testcase_68 | AC | 127 ms
77,772 KB |
testcase_69 | AC | 120 ms
77,832 KB |
testcase_70 | AC | 111 ms
77,680 KB |
testcase_71 | AC | 118 ms
77,828 KB |
testcase_72 | AC | 114 ms
77,568 KB |
testcase_73 | AC | 103 ms
77,032 KB |
testcase_74 | AC | 112 ms
78,064 KB |
testcase_75 | AC | 103 ms
76,884 KB |
testcase_76 | AC | 107 ms
77,644 KB |
testcase_77 | AC | 112 ms
77,644 KB |
testcase_78 | AC | 113 ms
78,008 KB |
testcase_79 | AC | 109 ms
77,944 KB |
testcase_80 | AC | 40 ms
54,740 KB |
testcase_81 | AC | 40 ms
55,340 KB |
testcase_82 | AC | 41 ms
54,240 KB |
testcase_83 | AC | 45 ms
55,820 KB |
testcase_84 | AC | 39 ms
54,112 KB |
testcase_85 | AC | 41 ms
54,260 KB |
testcase_86 | AC | 40 ms
56,172 KB |
testcase_87 | AC | 40 ms
55,036 KB |
testcase_88 | AC | 40 ms
55,500 KB |
testcase_89 | AC | 41 ms
54,444 KB |
testcase_90 | AC | 41 ms
54,248 KB |
testcase_91 | AC | 39 ms
55,120 KB |
testcase_92 | AC | 44 ms
55,516 KB |
testcase_93 | AC | 41 ms
55,492 KB |
testcase_94 | AC | 41 ms
54,708 KB |
testcase_95 | AC | 41 ms
55,496 KB |
testcase_96 | AC | 41 ms
55,272 KB |
testcase_97 | AC | 41 ms
55,876 KB |
testcase_98 | AC | 41 ms
55,108 KB |
testcase_99 | AC | 42 ms
56,072 KB |
testcase_100 | AC | 41 ms
54,792 KB |
testcase_101 | AC | 41 ms
56,072 KB |
testcase_102 | AC | 41 ms
55,572 KB |
testcase_103 | AC | 42 ms
55,632 KB |
testcase_104 | AC | 44 ms
54,600 KB |
testcase_105 | AC | 42 ms
54,492 KB |
testcase_106 | AC | 41 ms
55,372 KB |
testcase_107 | AC | 41 ms
54,244 KB |
testcase_108 | AC | 40 ms
55,372 KB |
testcase_109 | AC | 40 ms
55,040 KB |
testcase_110 | AC | 41 ms
54,508 KB |
testcase_111 | AC | 41 ms
55,808 KB |
testcase_112 | AC | 63 ms
70,484 KB |
testcase_113 | AC | 65 ms
70,540 KB |
testcase_114 | AC | 63 ms
69,780 KB |
testcase_115 | AC | 64 ms
70,596 KB |
testcase_116 | AC | 62 ms
70,452 KB |
testcase_117 | AC | 63 ms
71,120 KB |
testcase_118 | AC | 67 ms
70,124 KB |
testcase_119 | AC | 64 ms
69,512 KB |
testcase_120 | AC | 70 ms
71,504 KB |
testcase_121 | AC | 66 ms
71,632 KB |
testcase_122 | AC | 73 ms
71,356 KB |
testcase_123 | AC | 71 ms
71,424 KB |
testcase_124 | AC | 71 ms
71,172 KB |
testcase_125 | AC | 67 ms
69,960 KB |
testcase_126 | AC | 64 ms
71,716 KB |
testcase_127 | AC | 66 ms
70,864 KB |
testcase_128 | AC | 68 ms
72,728 KB |
testcase_129 | AC | 63 ms
70,636 KB |
testcase_130 | AC | 68 ms
72,808 KB |
testcase_131 | AC | 65 ms
69,716 KB |
testcase_132 | AC | 63 ms
70,192 KB |
testcase_133 | AC | 66 ms
71,084 KB |
testcase_134 | AC | 66 ms
71,444 KB |
testcase_135 | AC | 68 ms
72,144 KB |
testcase_136 | AC | 64 ms
70,252 KB |
testcase_137 | AC | 70 ms
69,524 KB |
testcase_138 | AC | 63 ms
70,848 KB |
testcase_139 | AC | 66 ms
71,772 KB |
testcase_140 | AC | 63 ms
70,196 KB |
testcase_141 | AC | 65 ms
71,164 KB |
testcase_142 | AC | 63 ms
70,144 KB |
testcase_143 | AC | 62 ms
70,696 KB |
ソースコード
#yukicoder 2822 Lights Up(Tree Edition) #offline LCA O(Nα(N) + Q) def offline_LCA(N, G, parent_v, Query): ans = [-1] * len(Query); Tasks = [[] for _ in range(N)]; *UF, = range(N); visit = []; T = [(parent_v, -1)] for q,(u,v) in enumerate(Query): if u == v: ans[q] = u else: Tasks[u].append((v,q)); Tasks[v].append((u,q)) def find(v): vertices = [] while UF[v] != v: vertices.append(v); v = UF[v] for i in vertices: UF[i] = v return v def unite(x,y): x,y = find(x), find(y) if x < y: UF[y] = x; return x else: UF[x] = y; return y while T: #pre-order counting now,back = T.pop(); visit.append(now) for next in G[now]: T.append((next,now)) if next != back else None R = {v:t for t,v in enumerate(visit)}; T = [(parent_v, -1)] while T: #LCA calculate now,back = T.pop() if now >= 0: #入りがけの処理 T.append((~now,back)); now_time = R[now] for next in G[now]: T.append((next,now)) if next != back else None for v,q in Tasks[now]: pair_time = R[v] if pair_time <= now_time: ans[q] = visit[find(pair_time)] else: p = R[~now]; unite(p, p-1) #帰りがけ処理。祖先情報を消す return ans #入力受取 N = int(input()) P = [-1] + list(map(lambda x: int(x) - 1, input().split())) S = [0] + [0 if Si == '.' else 1 for Si in input()] K = int(input()) T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(K)] #えーごめんなさい LCAはライブラリで甘えます・・・ nG = [[] for _ in range(N)] for now, Pi in enumerate(P[1:], start = 1): nG[now].append(Pi) nG[Pi].append(now) L = offline_LCA(N, nG, 0, T) #ETを用意 #visited[i][f]: 頂点iに(入りがけ / 出がけ)の時刻 visited = [[None] * 2 for _ in range(N)] arrival = [None] * 2 * N stack = [0] for t in range(2 * N): now = stack.pop() if now >= 0: #入りがけの処理 visited[now][0] = t stack.append(~now) arrival[t] = now for nxt in nG[now]: if visited[nxt][0] == None: stack.append(nxt) else: #帰りがけの処理 now = ~now visited[now][1] = t arrival[t] = now #辺の色の情報を配列Cに記録 辺は子の入りがけ番号に対応させる C = [0] * 2 * N for now, Pi in enumerate(P[1:], start = 1): t = visited[now][0] assert C[t] == 0 if S[now] == 1: C[t] = 1 #Cの差分列をとり、これをEとする E = [C[0]] + [abs(C[i] - C[i + 1]) for i in range(2 * N - 1)] + [C[-1]] #u - vパスを考える(ET訪問順はu < vとしてよい)。 #半開区間 (u入りがけ: v入りがけ] に該当する辺をxorにかければよい #[u_in + 1: v_in + 1)が反転するわけで、xorの差分を考えるとE[Lt], E[Rt] がxor反転する #あとは同じ辺同士も反転子を持つ必要がある これは後で処理 G = [[] for _ in range(2 * N + 1)] for Ui, Vi in T: Uv, Vv = visited[Ui][0], visited[Vi][0] if Uv > Vv: Uv, Vv = Vv, Uv G[Uv + 1].append(Vv + 1) G[Vv + 1].append(Uv + 1) #入りがけの時刻と出がけの時刻を同時に反転させてもよい for i in range(1, N): G[ visited[i][0] ].append( visited[i][1] + 1 ) G[ visited[i][1] + 1 ].append( visited[i][0] ) #後はDFS木を取って葉から貪欲 used = [False] * (2 * N + 1) for p in range(2 * N + 1): if used[p] == True: continue used[p] = True stack = [(p, -1)] for now, back in stack: assert used[now] == True for nxt in G[now]: if used[nxt] == False: used[nxt] = True stack.append((nxt, now)) while stack: now, back = stack.pop() for nxt in G[now]: if nxt != back and E[nxt] == 1: E[now], E[nxt] = E[now] ^ 1, E[nxt] ^ 1 #答えを出力 assert all(used) print('Yes' if not any(E) else 'No')