0w1

Doubling

JOI 11 本選 Festivals in JOI Kingdom ( MSSP Dijkstra + Kruskal + Doubling LCA )

Festivals in JOI Kingdom | Aizu Online Judge 先に全ての町について、一番近い祭りの距離を計算する。そして、最大全域木をその最短距離に基づき作る( 祭りに近い方からと遠い方から来ても、近い方を取る )とクエリ( u, v )に対しての答えは ( u, lca( u, …

ABC 14 D - 閉路 ( Doubling LCA )

D: 閉路 - AtCoder Beginner Contest 014 | AtCoder A small practice for doubling LCA. #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXQ = 1e5 + 5; const int LGN = 20; // 2 ^ 19 > 1e5 int n; vector<int> G[ MAXN ]; // connects</int></bits/stdc++.h>…

ABC 13 D - 阿弥陀 ( Doubling )

D: 阿弥陀 - AtCoder Beginner Contest 013 | AtCoder Without the variable D, we can simulate the process by swapping the numbers where edges exist, since making an edge on the bottom is equivalent to swapping the index of the two lines. We c…