[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
247: 2023/12/22(金)03:13 AAS
>>246
詳細：
部分問題：K を固定する. u,v を結ぶパスの頂点の中に重み K 以下のものがあるか？
という問題は頂点∪{K}を重み順にソートして, UnionFind で頂点重み大きい順からマージしていくと, いい感じのところで（だいたい）連結か非連結かで判定できる
これは Q 個のクエリに同時に行うこともできる. Q 個のクエリの K の最小値がすべて定まるまで繰り返せばよいが, O(log N) 回におさまる
上下前次1-新書関写板覧索設栞歴
あと 755 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.014s