結果

問題 No.2822 Lights Up! (Tree Edition)
ユーザー navel_tosnavel_tos
提出日時 2024-07-27 02:30:53
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,929 bytes
コンパイル時間 535 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 169,872 KB
最終ジャッジ日時 2024-07-27 02:31:20
合計ジャッジ時間 26,603 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
53,736 KB
testcase_01 AC 40 ms
53,852 KB
testcase_02 AC 684 ms
162,972 KB
testcase_03 WA -
testcase_04 AC 643 ms
162,840 KB
testcase_05 AC 733 ms
161,400 KB
testcase_06 AC 619 ms
169,872 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 617 ms
157,204 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 440 ms
124,660 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 168 ms
79,080 KB
testcase_18 WA -
testcase_19 AC 158 ms
80,584 KB
testcase_20 AC 179 ms
81,280 KB
testcase_21 WA -
testcase_22 AC 179 ms
85,192 KB
testcase_23 AC 187 ms
81,996 KB
testcase_24 AC 163 ms
80,936 KB
testcase_25 WA -
testcase_26 AC 185 ms
83,452 KB
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 176 ms
80,792 KB
testcase_32 AC 211 ms
87,356 KB
testcase_33 AC 204 ms
86,780 KB
testcase_34 WA -
testcase_35 AC 197 ms
87,100 KB
testcase_36 WA -
testcase_37 AC 202 ms
87,100 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 AC 193 ms
86,532 KB
testcase_42 AC 190 ms
86,876 KB
testcase_43 AC 209 ms
86,960 KB
testcase_44 AC 206 ms
87,324 KB
testcase_45 AC 231 ms
85,920 KB
testcase_46 AC 196 ms
86,772 KB
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 AC 116 ms
77,616 KB
testcase_52 AC 115 ms
77,748 KB
testcase_53 WA -
testcase_54 AC 114 ms
77,584 KB
testcase_55 WA -
testcase_56 AC 116 ms
77,676 KB
testcase_57 AC 113 ms
77,716 KB
testcase_58 AC 117 ms
77,876 KB
testcase_59 AC 119 ms
77,516 KB
testcase_60 AC 117 ms
77,616 KB
testcase_61 WA -
testcase_62 WA -
testcase_63 AC 121 ms
77,860 KB
testcase_64 AC 119 ms
77,716 KB
testcase_65 AC 118 ms
77,368 KB
testcase_66 WA -
testcase_67 WA -
testcase_68 WA -
testcase_69 WA -
testcase_70 WA -
testcase_71 AC 114 ms
77,588 KB
testcase_72 WA -
testcase_73 WA -
testcase_74 AC 117 ms
77,712 KB
testcase_75 AC 110 ms
77,512 KB
testcase_76 WA -
testcase_77 WA -
testcase_78 WA -
testcase_79 AC 116 ms
77,704 KB
testcase_80 WA -
testcase_81 WA -
testcase_82 AC 44 ms
55,564 KB
testcase_83 WA -
testcase_84 AC 43 ms
54,640 KB
testcase_85 AC 42 ms
55,796 KB
testcase_86 WA -
testcase_87 WA -
testcase_88 AC 43 ms
55,560 KB
testcase_89 AC 42 ms
55,276 KB
testcase_90 WA -
testcase_91 WA -
testcase_92 AC 44 ms
55,760 KB
testcase_93 WA -
testcase_94 WA -
testcase_95 AC 44 ms
55,488 KB
testcase_96 AC 43 ms
55,432 KB
testcase_97 AC 43 ms
55,764 KB
testcase_98 WA -
testcase_99 AC 43 ms
54,364 KB
testcase_100 WA -
testcase_101 WA -
testcase_102 WA -
testcase_103 AC 43 ms
54,856 KB
testcase_104 AC 43 ms
54,488 KB
testcase_105 WA -
testcase_106 WA -
testcase_107 WA -
testcase_108 WA -
testcase_109 WA -
testcase_110 WA -
testcase_111 WA -
testcase_112 AC 69 ms
70,064 KB
testcase_113 AC 68 ms
71,048 KB
testcase_114 WA -
testcase_115 WA -
testcase_116 AC 68 ms
69,836 KB
testcase_117 AC 71 ms
70,996 KB
testcase_118 WA -
testcase_119 AC 67 ms
68,748 KB
testcase_120 WA -
testcase_121 WA -
testcase_122 WA -
testcase_123 AC 70 ms
70,944 KB
testcase_124 WA -
testcase_125 WA -
testcase_126 WA -
testcase_127 WA -
testcase_128 AC 71 ms
71,384 KB
testcase_129 WA -
testcase_130 WA -
testcase_131 WA -
testcase_132 WA -
testcase_133 AC 72 ms
71,648 KB
testcase_134 AC 71 ms
70,848 KB
testcase_135 WA -
testcase_136 AC 69 ms
70,668 KB
testcase_137 WA -
testcase_138 AC 66 ms
70,864 KB
testcase_139 AC 67 ms
70,120 KB
testcase_140 AC 68 ms
70,440 KB
testcase_141 AC 72 ms
73,152 KB
testcase_142 AC 72 ms
70,760 KB
testcase_143 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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(N):
    G[ visited[i][0] ].append( visited[i][1] )
    G[ visited[i][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')
0