結果
問題 | No.2403 "Eight" Bridges of Königsberg |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2023-08-04 22:45:16 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,917 bytes |
コンパイル時間 | 844 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 114,944 KB |
最終ジャッジ日時 | 2024-10-14 20:48:14 |
合計ジャッジ時間 | 4,911 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
52,224 KB |
testcase_01 | AC | 39 ms
52,096 KB |
testcase_02 | AC | 39 ms
52,096 KB |
testcase_03 | WA | - |
testcase_04 | AC | 135 ms
76,288 KB |
testcase_05 | AC | 182 ms
76,672 KB |
testcase_06 | AC | 192 ms
77,184 KB |
testcase_07 | AC | 146 ms
76,288 KB |
testcase_08 | AC | 175 ms
76,672 KB |
testcase_09 | AC | 200 ms
77,056 KB |
testcase_10 | AC | 183 ms
76,288 KB |
testcase_11 | AC | 175 ms
76,544 KB |
testcase_12 | AC | 193 ms
76,416 KB |
testcase_13 | AC | 178 ms
76,928 KB |
testcase_14 | AC | 40 ms
52,224 KB |
testcase_15 | AC | 39 ms
51,968 KB |
testcase_16 | WA | - |
testcase_17 | AC | 40 ms
51,712 KB |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
ソースコード
""" https://yukicoder.me/problems/no/2403 オイラー路を作れってこと 全体を連結にする まず、全体が連結じゃないと駄目なんだよな… in , out が打ち消し合って居ない場合… 連結成分ごとに in/outの欲しい個数を書いておくか… 後は? 連結成分内で、in/outの溢れ個数は同じ? だな とりあえずくっ付ける必要はある i/o を1つずつ消費してくっ付けられる a,b -> a+b-1 になる 1,1 -> 1 なので…? 0以外は適当にくっ付けてokっぽい 適当にくっ付けた後、 0 をくっ付ける必要がある。 1,1 0,0 -> 1,1 になる """ import sys from sys import stdin def uf_find(n,p): ufl = [] while p[n] != n: ufl.append(n) n = p[n] for i in ufl: p[i] = n return n def uf_union(a,b,p,rank): ap = uf_find(a,p) bp = uf_find(b,p) if ap == bp: return True else: if rank[ap] > rank[bp]: p[bp] = ap elif rank[ap] < rank[bp]: p[ap] = bp else: p[bp] = ap rank[ap] += 1 return False N,M = map(int,stdin.readline().split()) D = [0] * N p = [i for i in range(N)] rank = [0] * N for i in range(M): u,v = map(int,stdin.readline().split()) u -= 1 v -= 1 uf_union(u,v,p,rank) D[u] += 1 D[v] -= 1 dic = {} #print (D) for i in range(N): np = uf_find(i,p) if np not in dic: dic[np] = 0 if D[i] > 0: dic[np] += D[i] lis = [] for i in dic: lis.append(dic[i]) lis.sort() print (lis,file=sys.stderr) ans = 0 while len(lis) >= 2: r = lis.pop() l = lis.pop() if l == 0 and r == 0: ans += 1 lis.append(1) elif l == 0: ans += 1 lis.append(r) else: ans += 1 lis.append(l+r-1) ans += max(0,lis[0]-1) print (ans)