[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
252(2): 2023/12/22(金)03:55 AAS
>>250
そんな感じになるが、下限と上限の配列 ng(Q), ok(Q) を用意して log N 回行う：
1. 配列 t(Q) を, t[i] = (ng[i] + ok[i]) / 2 で定める
2. t(Q) と頂点を一緒にして重み降順ソートする
3. N 要素の UnionFind を用意する
4. 頂点重みの大きいほうから見ていく, t(Q) の要素にぶつかったら判定
5. i 番目の判定が true なら ok(i) ← t, そうでなければ ng(i) ← t
省1
255(1): 2023/12/22(金)04:04 AAS
>>252
合っててよかった
計算量にlog^2の項は生えないはず 辺の重みソートは初回だけでよいので
256: 252 2023/12/22(金)04:07 AAS
>>255
たしかに
サボらずにちゃんとやればソートでかかる log は落ちるか（自分はめんどくさくて生やしてしまいそう）
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.031s