#961671 (PyPy3) No.2677 Minmax Independent Set

提出ソース

結果

問題	No.2677 Minmax Independent Set
ユーザー	titia
提出日時	2024-03-19 03:18:07
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,011 ms / 2,000 ms
コード長	2,718 bytes
コンパイル時間	226 ms
コンパイル使用メモリ	82,228 KB
実行使用メモリ	220,868 KB
最終ジャッジ日時	2024-09-30 05:14:09
合計ジャッジ時間	31,547 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	34 ms 53,092 KB
testcase_01	AC	37 ms 54,080 KB
testcase_02	AC	33 ms 53,380 KB
testcase_03	AC	35 ms 53,432 KB
testcase_04	AC	35 ms 53,928 KB
testcase_05	AC	828 ms 197,856 KB
testcase_06	AC	858 ms 197,580 KB
testcase_07	AC	834 ms 197,612 KB
testcase_08	AC	818 ms 197,628 KB
testcase_09	AC	844 ms 197,740 KB
testcase_10	AC	841 ms 219,640 KB
testcase_11	AC	789 ms 220,304 KB
testcase_12	AC	493 ms 195,004 KB
testcase_13	AC	869 ms 208,376 KB
testcase_14	AC	901 ms 215,536 KB
testcase_15	AC	926 ms 207,760 KB
testcase_16	AC	959 ms 201,732 KB
testcase_17	AC	919 ms 200,000 KB
testcase_18	AC	621 ms 156,132 KB
testcase_19	AC	722 ms 169,188 KB
testcase_20	AC	270 ms 107,928 KB
testcase_21	AC	796 ms 180,624 KB
testcase_22	AC	137 ms 83,272 KB
testcase_23	AC	51 ms 64,384 KB
testcase_24	AC	38 ms 53,760 KB
testcase_25	AC	38 ms 53,120 KB
testcase_26	AC	39 ms 53,888 KB
testcase_27	AC	47 ms 62,592 KB
testcase_28	AC	761 ms 220,744 KB
testcase_29	AC	803 ms 195,120 KB
testcase_30	AC	38 ms 52,224 KB
testcase_31	AC	37 ms 52,608 KB
testcase_32	AC	38 ms 52,096 KB
testcase_33	AC	38 ms 52,736 KB
testcase_34	AC	38 ms 52,608 KB
testcase_35	AC	39 ms 52,992 KB
testcase_36	AC	40 ms 54,016 KB
testcase_37	AC	46 ms 59,904 KB
testcase_38	AC	53 ms 65,536 KB
testcase_39	AC	98 ms 77,212 KB
testcase_40	AC	119 ms 78,640 KB
testcase_41	AC	152 ms 80,832 KB
testcase_42	AC	156 ms 82,252 KB
testcase_43	AC	193 ms 88,448 KB
testcase_44	AC	289 ms 106,052 KB
testcase_45	AC	519 ms 137,860 KB
testcase_46	AC	996 ms 198,236 KB
testcase_47	AC	1,011 ms 200,416 KB
testcase_48	AC	975 ms 200,852 KB
testcase_49	AC	989 ms 200,448 KB
testcase_50	AC	324 ms 130,352 KB
testcase_51	AC	92 ms 78,848 KB
testcase_52	AC	694 ms 197,176 KB
testcase_53	AC	600 ms 185,588 KB
testcase_54	AC	91 ms 78,976 KB
testcase_55	AC	786 ms 215,136 KB
testcase_56	AC	789 ms 216,324 KB
testcase_57	AC	785 ms 219,380 KB
testcase_58	AC	786 ms 220,868 KB
testcase_59	AC	785 ms 215,788 KB
testcase_60	AC	470 ms 205,104 KB
testcase_61	AC	445 ms 201,360 KB
testcase_62	AC	452 ms 198,016 KB
testcase_63	AC	448 ms 200,004 KB

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

ソースコード

raw source code

import sys
input = sys.stdin.readline

n=int(input())
E=[[] for i in range(n)]

for i in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    E[u].append(v)
    E[v].append(u)

ROOT=0
 
QUE=[ROOT] 
Parent=[-1]*n
Parent[ROOT]=n # ROOTの親を定めておく.
Child=[[] for i in range(n)]
TOP_SORT=[] # トポロジカルソート
 
while QUE: # トポロジカルソートと同時に親を見つける
    x=QUE.pop()
    TOP_SORT.append(x)
    for to in E[x]:
        if Parent[to]==-1:
            Parent[to]=x
            Child[x].append(to)
            QUE.append(to)
 
UP=[[0,0] for i in range(n)]
DOWN=[[0,0] for i in range(n)]
 
# xとParent[x]をつなぐedgeを考える
# UP[x]は、xをROOTとする部分木に関する値。
# xとつながるnodeのうち、Parent[x]以外をxの子と捉える。
 
# DOWN[x]はParent[x]をROOTとする部分木に関する値。
# Parent[x]とつながるnodeのうち、x以外をParent[x]の子と捉える。
 
def compose_calc(x,y):# 子たちの値を合成する
    return [x[0]+y[0],x[1]+y[1]]
 
unit=[0,0] # 単位元
# 次OK, 次ダメ 
def final_ans(x,value):# 子たちから計算した値から答えを出す
    return [x[1],max(x[1],x[0]+1)]


for x in TOP_SORT[::-1]:
    if Child[x]==[]:
        UP[x]=[0,1]
        continue
    
    k=unit # 子が全て1なら0、それ以外は1
    for c in Child[x]:
        k=compose_calc(k,UP[c])
 
    UP[x]=final_ans(k,0)
 
COMPOSE=[unit]*n
no_composed_value=[0,0] #composeされないときの値
 
# DOWN[x]を求めるときに使う
# Parent[x]について、Parent[Parent[x]]以外からの寄与。
# 各iについて、for c in Child[i]についてUP[c]の値をみて、左右からの累積和を使って計算。
 
for i in range(n):
    X=[]
    for c in Child[i]:
        X.append(UP[c])
 
    if X==[]:
        continue
 
    LEFT=[X[0]]
    for j in range(1,len(X)):
        LEFT.append(compose_calc(LEFT[-1],X[j]))
 
    RIGHT=no_composed_value
    for j in range(len(X)-1,-1,-1):
        if j!=0:
            COMPOSE[Child[i][j]]=compose_calc(LEFT[j-1],RIGHT)
        else:
            COMPOSE[Child[i][j]]=RIGHT
 
        RIGHT=compose_calc(RIGHT,X[j])
 
for x in TOP_SORT:
    if x==ROOT:
        DOWN[x]=[0,0]
        continue
 
    p=Parent[x]
    
    if p==ROOT:
        k=COMPOSE[x]
    else:
        k=compose_calc(DOWN[p],COMPOSE[x])
 
    DOWN[x]=final_ans(k,0)
 
 
ANS=[0]*n
# iをROOTとしたときの値は、
# for c in Child[i]についてのUP[c]とDOWN[i]から求められる。
for i in range(n):
    k=unit
    for c in Child[i]:
        k=compose_calc(k,UP[c])
 
    if i!=ROOT:
        k=compose_calc(k,DOWN[i])
 
    ANS[i]=k[0]

print(min(ANS)+1)

yukicoder

結果

テストケース

ソースコード