Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

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>…

Lowest common ancestor

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…