質問編集履歴
1
プログラムの概要や、試したことの追記
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,4 +1,5 @@
|
|
|
1
1
|
Atcoder ABC282 D問題
|
|
2
|
+
https://atcoder.jp/contests/abc282/tasks/abc282_d
|
|
2
3
|
TLEの原因が分かりません
|
|
3
4
|
|
|
4
5
|
以下のコードに対して、
|
|
@@ -7,6 +8,18 @@
|
|
|
7
8
|
この入力に対して、各colは計算量O(１)ではないのでしょうか？
|
|
8
9
|
|
|
9
10
|
どなたか回答よろしくお願いします。
|
|
11
|
+
|
|
12
|
+
プログラムの概要：
|
|
13
|
+
・入力に対して、グラフの作成とunion-find木の作成を同時に行う。
|
|
14
|
+
・col関数で、各独立した木に対して(union-findで取得した根が属する木に対して)二分グラフの判定および白黒の割り当てを行う
|
|
15
|
+
・n*(n-1)//2から、辺の本数であるｍと二分グラフで得た白同士黒同士で結ぶことのできない組み合わせを引く
|
|
16
|
+
|
|
17
|
+
試したこと：
|
|
18
|
+
・sampleはすべて通る
|
|
19
|
+
・提出の結果、半分ほどがTLEになり、他はAC
|
|
20
|
+
・10000 0などの入力に対してTLEになることから、nが大きい場合に失敗すると考えている
|
|
21
|
+
・入力(10 0)でcol関数のwhileの直後にprint(keep)を行っても、無駄なループが発生している様子はない
|
|
22
|
+
|
|
10
23
|
|
|
11
24
|
```Python
|
|
12
25
|
from collections import deque
|