結果

問題 No.2822 Lights Up! (Tree Edition)
コンテスト
ユーザー chineristAC
提出日時 2024-07-26 21:47:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 183 ms / 2,000 ms
コード長 2,986 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 104,868 KB
最終ジャッジ日時 2024-07-26 21:47:38
合計ジャッジ時間 14,099 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 142
権限があれば一括ダウンロードができます

ソースコード

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] + flip[i]
    
    
    
    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"

def solve_brute(N,P,S,K,op):
    parent = [-1] + [p-1 for p in P]
    dep = [0] * N
    for i in range(1,N):
        dep[i] = dep[parent[i]] + 1
    
    def opearate(u,v,tmp):
        if dep[u] < dep[v]:
            u,v = v,u
        
        while dep[u]!=dep[v]:
            tmp[u] ^= 1
            u = parent[u]
        
        while u!=v:
            tmp[u] ^= 1
            tmp[v] ^= 1
            u = parent[u]
            v = parent[v]
    
    for op_set in range(1<<K):
        tmp = [0] + [int(S[i]=="#") for i in range(N-1)]
        for i in range(K):
            if op_set>>i & 1:
                u,v = op[i]
                u,v = u-1,v-1
                opearate(u,v,tmp)
        
        if sum(tmp) == 0:
            return "Yes"
    
    return "No"

def make_test(N,K):
    P = []
    for i in range(1,N):
        pi = random.randint(0,i-1)
        P.append(pi+1)
    
    S = "".join([random.choice(".#") for i in range(N-1)])
    op = []
    for _ in range(K):
        u,v = random.randint(0,N-1),random.randint(0,N-1)
        while u==v:
            u,v = random.randint(0,N-1),random.randint(0,N-1)
        op.append((u+1,v+1))
    
    return P,S,op

while False:
    N = random.randint(2,10)
    K = random.randint(1,7)
    P,S,op = make_test(N,K)

    #N,K = 5,4
    #P = [1,1,3,4]
    #S = "#.##"
    #op = [(4,2),(2,5),(1,4),(2,1)]

    exp = solve_brute(N,P,S,K,op)
    res = solve(N,P,S,K,op)

    if exp!=res:
        print("WA")
        print(N,K)
        print(P)
        print(S)
        print(op)
        print(exp,res)
        exit()
    else:
        print("AC",exp)

            


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