結果

問題 No.2822 Lights Up! (Tree Edition)
コンテスト
ユーザー navel_tos
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 142
権限があれば一括ダウンロードができます

ソースコード

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(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')
0