結果

問題 No.2822 Lights Up! (Tree Edition)
ユーザー navel_tosnavel_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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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
権限があれば一括ダウンロードができます

ソースコード

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