結果

問題 No.2822 Lights Up! (Tree Edition)
ユーザー chineristAC
提出日時 2024-07-26 21:34:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,354 bytes
コンパイル時間 135 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 104,992 KB
最終ジャッジ日時 2024-07-26 21:34:38
合計ジャッジ時間 12,866 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 69 WA * 73
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import permutations
from heapq import *
from collections import deque
import random
import bisect
from math import factorial

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

def solve(N,P,S,K,op):
    parent = [-1] + [p-1 for p in P]

    flip = [0] * N
    tmp_sum = [0] * N
    for i in range(1,N)[::-1]:
        check = int(S[i-1] == "#")
        flip[i] = check ^ (tmp_sum[i] & 1)
        tmp_sum[parent[i]] += tmp_sum[i] + check
    
    edge = [[] for v in range(N)]
    for u,v in op:
        edge[u-1].append(v-1)
        edge[v-1].append(u-1)

    for x in range(2):
        flip[0] = x
        visit = [False] * N
        
        for s in range(N):
            if visit[s]:
                continue

            st = [s]
            tmp = 0
            visit[s] = True
            while st:
                v = st.pop()
                tmp ^= flip[v]
                for nv in edge[v]:
                    if not visit[nv]:
                        visit[nv] = True
                        st.append(nv)
            
            if tmp == 1:
                break
        else:
            return "Yes"

    return "No"

N = int(input())
P = li()
S = input()
K = int(input())
op = [tuple(mi()) for i in range(K)]
print(solve(N,P,S,K,op))
0