search

beet-aizu / library

Competitive Programming Library
https://beet-aizu.github.io/library/
128 stars 23 forks source link

TopTree 頂点数 決め方 #92

Closed beet-aizu closed 3 years ago

beet-aizu commented 3 years ago

ちゃんと定式化しないと定数倍バトルで苦しむ

beet-aizu commented 3 years ago

Node *p を転用して linked list をつくれば O(1) で Node の再利用ができるじゃん

beet-aizu commented 3 years ago

Node *p を転用して linked list をつくれば O(1) で Node の再利用ができるじゃん

done in f49fca56eebd297e2ec92a95bdbef04ae8e124e5 （後半はなんか不要な場合分け入れてたので消したやつ）

beet-aizu commented 3 years ago

dummy ありの場合

ので、Node は (2N - 1) * 2 - 1 <= 4N くらいあればよいはず

beet-aizu commented 3 years ago

どうして… https://yukicoder.me/submissions/689860 https://yukicoder.me/submissions/689866

beet-aizu commented 3 years ago

4N で収まってないやん！　cut で回収しきれてないのか？ https://yukicoder.me/submissions/689867/print/stderr/0121.txt

beet-aizu commented 3 years ago

https://yukicoder.me/submissions/689871 rake を splay して上に持ってきたらそいつはもういらん

beet-aizu commented 3 years ago

とりあえず close