#997604 (PyPy3) No.2822 Lights Up! (Tree Edition)

提出ソース

結果

問題	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	45 ms 56,760 KB
testcase_01	AC	45 ms 57,232 KB
testcase_02	AC	176 ms 94,364 KB
testcase_03	AC	165 ms 95,884 KB
testcase_04	AC	157 ms 95,904 KB
testcase_05	AC	166 ms 95,644 KB
testcase_06	AC	158 ms 104,868 KB
testcase_07	AC	171 ms 100,388 KB
testcase_08	AC	134 ms 89,444 KB
testcase_09	AC	147 ms 91,368 KB
testcase_10	AC	183 ms 92,628 KB
testcase_11	AC	117 ms 88,000 KB
testcase_12	AC	140 ms 94,308 KB
testcase_13	AC	140 ms 85,568 KB
testcase_14	AC	142 ms 88,836 KB
testcase_15	AC	128 ms 87,792 KB
testcase_16	AC	66 ms 72,596 KB
testcase_17	AC	65 ms 73,616 KB
testcase_18	AC	80 ms 78,328 KB
testcase_19	AC	60 ms 70,924 KB
testcase_20	AC	72 ms 78,144 KB
testcase_21	AC	83 ms 78,168 KB
testcase_22	AC	73 ms 78,228 KB
testcase_23	AC	78 ms 78,380 KB
testcase_24	AC	66 ms 73,512 KB
testcase_25	AC	63 ms 70,756 KB
testcase_26	AC	75 ms 78,516 KB
testcase_27	AC	64 ms 69,996 KB
testcase_28	AC	90 ms 78,532 KB
testcase_29	AC	108 ms 78,804 KB
testcase_30	AC	83 ms 78,568 KB
testcase_31	AC	73 ms 78,036 KB
testcase_32	AC	81 ms 78,508 KB
testcase_33	AC	79 ms 78,332 KB
testcase_34	AC	81 ms 78,076 KB
testcase_35	AC	75 ms 78,088 KB
testcase_36	AC	82 ms 78,384 KB
testcase_37	AC	78 ms 78,088 KB
testcase_38	AC	84 ms 78,068 KB
testcase_39	AC	84 ms 78,044 KB
testcase_40	AC	79 ms 78,412 KB
testcase_41	AC	75 ms 78,068 KB
testcase_42	AC	78 ms 78,080 KB
testcase_43	AC	77 ms 78,552 KB
testcase_44	AC	75 ms 78,444 KB
testcase_45	AC	84 ms 78,088 KB
testcase_46	AC	76 ms 78,100 KB
testcase_47	AC	94 ms 79,084 KB
testcase_48	AC	58 ms 67,372 KB
testcase_49	AC	62 ms 67,928 KB
testcase_50	AC	61 ms 68,712 KB
testcase_51	AC	54 ms 65,536 KB
testcase_52	AC	56 ms 66,880 KB
testcase_53	AC	55 ms 66,892 KB
testcase_54	AC	52 ms 65,744 KB
testcase_55	AC	55 ms 67,852 KB
testcase_56	AC	53 ms 66,988 KB
testcase_57	AC	55 ms 67,192 KB
testcase_58	AC	54 ms 66,472 KB
testcase_59	AC	53 ms 67,176 KB
testcase_60	AC	54 ms 67,544 KB
testcase_61	AC	57 ms 66,308 KB
testcase_62	AC	57 ms 66,556 KB
testcase_63	AC	54 ms 65,468 KB
testcase_64	AC	54 ms 66,460 KB
testcase_65	AC	55 ms 67,520 KB
testcase_66	AC	60 ms 66,928 KB
testcase_67	AC	60 ms 66,304 KB
testcase_68	AC	60 ms 66,784 KB
testcase_69	AC	62 ms 66,640 KB
testcase_70	AC	56 ms 67,428 KB
testcase_71	AC	60 ms 66,836 KB
testcase_72	AC	60 ms 66,936 KB
testcase_73	AC	56 ms 68,288 KB
testcase_74	AC	56 ms 66,728 KB
testcase_75	AC	55 ms 65,752 KB
testcase_76	AC	66 ms 69,632 KB
testcase_77	AC	57 ms 67,404 KB
testcase_78	AC	57 ms 67,988 KB
testcase_79	AC	53 ms 67,208 KB
testcase_80	AC	48 ms 58,920 KB
testcase_81	AC	48 ms 57,936 KB
testcase_82	AC	48 ms 58,564 KB
testcase_83	AC	47 ms 57,168 KB
testcase_84	AC	45 ms 57,476 KB
testcase_85	AC	46 ms 58,252 KB
testcase_86	AC	47 ms 57,124 KB
testcase_87	AC	47 ms 57,564 KB
testcase_88	AC	46 ms 57,972 KB
testcase_89	AC	45 ms 57,972 KB
testcase_90	AC	45 ms 58,108 KB
testcase_91	AC	45 ms 58,040 KB
testcase_92	AC	46 ms 58,236 KB
testcase_93	AC	45 ms 57,928 KB
testcase_94	AC	44 ms 58,456 KB
testcase_95	AC	45 ms 58,156 KB
testcase_96	AC	50 ms 57,488 KB
testcase_97	AC	45 ms 56,816 KB
testcase_98	AC	46 ms 57,640 KB
testcase_99	AC	45 ms 57,132 KB
testcase_100	AC	46 ms 57,572 KB
testcase_101	AC	47 ms 56,980 KB
testcase_102	AC	45 ms 58,108 KB
testcase_103	AC	46 ms 57,496 KB
testcase_104	AC	45 ms 57,672 KB
testcase_105	AC	46 ms 57,740 KB
testcase_106	AC	46 ms 58,608 KB
testcase_107	AC	51 ms 57,320 KB
testcase_108	AC	46 ms 58,848 KB
testcase_109	AC	44 ms 57,804 KB
testcase_110	AC	45 ms 56,884 KB
testcase_111	AC	45 ms 57,324 KB
testcase_112	AC	52 ms 64,880 KB
testcase_113	AC	55 ms 65,712 KB
testcase_114	AC	54 ms 65,280 KB
testcase_115	AC	52 ms 65,804 KB
testcase_116	AC	56 ms 64,924 KB
testcase_117	AC	58 ms 66,396 KB
testcase_118	AC	58 ms 65,548 KB
testcase_119	AC	55 ms 65,224 KB
testcase_120	AC	53 ms 65,308 KB
testcase_121	AC	54 ms 65,704 KB
testcase_122	AC	54 ms 65,444 KB
testcase_123	AC	52 ms 65,068 KB
testcase_124	AC	52 ms 65,936 KB
testcase_125	AC	53 ms 66,656 KB
testcase_126	AC	57 ms 64,604 KB
testcase_127	AC	57 ms 66,796 KB
testcase_128	AC	57 ms 65,328 KB
testcase_129	AC	57 ms 65,272 KB
testcase_130	AC	58 ms 65,284 KB
testcase_131	AC	58 ms 65,636 KB
testcase_132	AC	57 ms 66,360 KB
testcase_133	AC	54 ms 66,932 KB
testcase_134	AC	54 ms 65,924 KB
testcase_135	AC	53 ms 66,540 KB
testcase_136	AC	54 ms 65,828 KB
testcase_137	AC	57 ms 66,176 KB
testcase_138	AC	55 ms 65,272 KB
testcase_139	AC	58 ms 65,076 KB
testcase_140	AC	54 ms 65,608 KB
testcase_141	AC	54 ms 65,148 KB
testcase_142	AC	53 ms 64,796 KB
testcase_143	AC	59 ms 66,308 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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))

yukicoder

結果

テストケース

ソースコード