結果

問題 No.317 辺の追加
ユーザー tjaketjake
提出日時 2015-12-16 01:47:52
言語 PyPy2
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,113 bytes
コンパイル時間 744 ms
コンパイル使用メモリ 77,448 KB
実行使用メモリ 128,904 KB
最終ジャッジ日時 2023-10-14 10:33:29
合計ジャッジ時間 27,007 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 80 ms
78,308 KB
testcase_01 AC 81 ms
78,324 KB
testcase_02 AC 289 ms
108,224 KB
testcase_03 AC 281 ms
111,532 KB
testcase_04 AC 371 ms
104,464 KB
testcase_05 AC 257 ms
111,836 KB
testcase_06 AC 310 ms
120,076 KB
testcase_07 AC 172 ms
93,000 KB
testcase_08 AC 644 ms
104,052 KB
testcase_09 AC 372 ms
113,744 KB
testcase_10 AC 350 ms
124,452 KB
testcase_11 AC 225 ms
93,608 KB
testcase_12 AC 335 ms
124,404 KB
testcase_13 AC 260 ms
97,088 KB
testcase_14 AC 354 ms
118,364 KB
testcase_15 AC 357 ms
125,456 KB
testcase_16 AC 381 ms
107,988 KB
testcase_17 AC 342 ms
119,080 KB
testcase_18 AC 369 ms
124,184 KB
testcase_19 AC 395 ms
128,904 KB
testcase_20 AC 421 ms
106,056 KB
testcase_21 AC 178 ms
96,076 KB
testcase_22 AC 154 ms
89,344 KB
testcase_23 RE -
testcase_24 AC 215 ms
107,384 KB
testcase_25 AC 202 ms
100,320 KB
testcase_26 AC 204 ms
101,624 KB
testcase_27 AC 185 ms
96,872 KB
testcase_28 AC 181 ms
90,160 KB
testcase_29 AC 119 ms
82,552 KB
testcase_30 AC 1,143 ms
112,548 KB
testcase_31 AC 1,283 ms
112,544 KB
testcase_32 AC 1,266 ms
112,572 KB
testcase_33 AC 1,282 ms
112,336 KB
testcase_34 AC 1,268 ms
112,360 KB
testcase_35 AC 1,276 ms
112,484 KB
testcase_36 AC 1,255 ms
112,336 KB
testcase_37 AC 1,300 ms
112,424 KB
testcase_38 AC 1,087 ms
112,328 KB
testcase_39 AC 1,242 ms
112,340 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque, Counter
from sys import stdin, stdout
ss = [map(int, s.split()) for s in stdin.readlines()]
n, m = ss[0]
n1 = n+1
g = [[] for i in xrange(n1)]
for u, v in ss[1:]:
    g[u].append(v)
    g[v].append(u)

ct = Counter()

deq = deque()
clear = deq.clear
pop = deq.pop
popleft = deq.popleft
append = deq.append

used = [1]+[0]*n
for i in xrange(n1):
    if not used[i]:
        used[i] = 1
        cnt = 1
        append(i)
        while deq:
            v = popleft()
            for t in g[v]:
                if not used[t]:
                    used[t] = 1
                    append(t)
                    cnt += 1
        ct[cnt] += 1

dp = [-1]+[n]*n
for i, c in ct.items():
    for a in xrange(i):
        clear()
        for j in xrange((n-a)/i+1):
            idx = j*i+a
            p = (dp[idx]-j, -j)
            while deq and p <= deq[-1]:
                pop()
            append(p)
            v, u = deq[0]
            dp[idx] = v + j
            if c==j+u:
                popleft()

dp = [v if v!=n else -1 for v in dp]
stdout.write("\n".join(map(str, dp[1:])) + "\n")
0