結果
問題 | No.2677 Minmax Independent Set |
ユーザー | titia |
提出日時 | 2024-03-19 03:18:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 981 ms / 2,000 ms |
コード長 | 2,718 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 221,088 KB |
最終ジャッジ日時 | 2024-03-19 03:19:03 |
合計ジャッジ時間 | 30,950 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
53,460 KB |
testcase_01 | AC | 35 ms
53,460 KB |
testcase_02 | AC | 34 ms
53,460 KB |
testcase_03 | AC | 41 ms
53,460 KB |
testcase_04 | AC | 36 ms
53,460 KB |
testcase_05 | AC | 863 ms
197,720 KB |
testcase_06 | AC | 981 ms
197,452 KB |
testcase_07 | AC | 829 ms
197,472 KB |
testcase_08 | AC | 806 ms
197,360 KB |
testcase_09 | AC | 823 ms
197,596 KB |
testcase_10 | AC | 811 ms
219,912 KB |
testcase_11 | AC | 766 ms
219,924 KB |
testcase_12 | AC | 512 ms
194,356 KB |
testcase_13 | AC | 821 ms
208,228 KB |
testcase_14 | AC | 836 ms
215,004 KB |
testcase_15 | AC | 876 ms
207,596 KB |
testcase_16 | AC | 914 ms
201,204 KB |
testcase_17 | AC | 870 ms
199,852 KB |
testcase_18 | AC | 590 ms
156,152 KB |
testcase_19 | AC | 696 ms
168,888 KB |
testcase_20 | AC | 267 ms
107,508 KB |
testcase_21 | AC | 718 ms
180,312 KB |
testcase_22 | AC | 143 ms
83,096 KB |
testcase_23 | AC | 60 ms
65,928 KB |
testcase_24 | AC | 38 ms
55,592 KB |
testcase_25 | AC | 36 ms
53,460 KB |
testcase_26 | AC | 39 ms
55,592 KB |
testcase_27 | AC | 46 ms
63,880 KB |
testcase_28 | AC | 685 ms
220,472 KB |
testcase_29 | AC | 763 ms
194,732 KB |
testcase_30 | AC | 36 ms
53,460 KB |
testcase_31 | AC | 35 ms
53,460 KB |
testcase_32 | AC | 36 ms
53,460 KB |
testcase_33 | AC | 36 ms
53,460 KB |
testcase_34 | AC | 37 ms
53,460 KB |
testcase_35 | AC | 37 ms
53,460 KB |
testcase_36 | AC | 38 ms
55,592 KB |
testcase_37 | AC | 44 ms
60,740 KB |
testcase_38 | AC | 52 ms
66,076 KB |
testcase_39 | AC | 92 ms
76,908 KB |
testcase_40 | AC | 125 ms
78,312 KB |
testcase_41 | AC | 151 ms
80,680 KB |
testcase_42 | AC | 148 ms
82,160 KB |
testcase_43 | AC | 176 ms
88,188 KB |
testcase_44 | AC | 270 ms
105,568 KB |
testcase_45 | AC | 493 ms
137,332 KB |
testcase_46 | AC | 873 ms
198,308 KB |
testcase_47 | AC | 966 ms
200,144 KB |
testcase_48 | AC | 921 ms
200,584 KB |
testcase_49 | AC | 925 ms
200,048 KB |
testcase_50 | AC | 300 ms
130,456 KB |
testcase_51 | AC | 92 ms
79,104 KB |
testcase_52 | AC | 613 ms
196,908 KB |
testcase_53 | AC | 571 ms
185,436 KB |
testcase_54 | AC | 89 ms
78,612 KB |
testcase_55 | AC | 741 ms
215,100 KB |
testcase_56 | AC | 736 ms
215,824 KB |
testcase_57 | AC | 761 ms
219,576 KB |
testcase_58 | AC | 751 ms
221,088 KB |
testcase_59 | AC | 765 ms
215,512 KB |
testcase_60 | AC | 452 ms
204,964 KB |
testcase_61 | AC | 455 ms
201,216 KB |
testcase_62 | AC | 425 ms
197,492 KB |
testcase_63 | AC | 454 ms
199,740 KB |
ソースコード
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)