Created
December 27, 2020 14:17
-
-
Save mbrc12/247b5025d3179e05eb8fd765679aad34 to your computer and use it in GitHub Desktop.
HLD code
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#define DEBUG | |
#define LARGEINT | |
#include <bits/stdc++.h> | |
#include <ext/pb_ds/assoc_container.hpp> | |
#include <ext/pb_ds/tree_policy.hpp> | |
#include <fmt/core.h> | |
using namespace __gnu_pbds; | |
using namespace std; | |
#ifdef LARGEINT | |
#define int ll | |
#endif | |
typedef long long ll; | |
namespace basics { | |
typedef long double ld; | |
typedef pair<int, int> pii; | |
typedef pair<ld, ld> point; | |
const long long mod = 1e9 + 7; | |
// To remove randomization use 0 below: | |
/* mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); */ | |
mt19937 rng(5); | |
inline int ri(int x) { // from [0, n-1] | |
return uniform_int_distribution<int>(0, x - 1)(rng); | |
} | |
inline ld rf() { // from [0, 1] | |
return uniform_real_distribution<ld>(0, 1)(rng); | |
} | |
ll gcd(ll x, ll y) { | |
if (x < y) return gcd(y, x); | |
if (y == 0) return x; | |
return gcd(y, x % y); | |
} | |
ll modexp(ll x, ll ex) { | |
ll ans = 1ll; | |
while (ex > 0) { | |
if (ex & 1ll) ans = (ans * x) % mod; | |
ex >>= 1ll; | |
x = (x * x) % mod; | |
} | |
return ans; | |
} | |
} | |
namespace io { | |
istringstream _inp; | |
string _inps; | |
void common() { | |
_inp.clear(); | |
_inps = ""; | |
_inp.str(_inps); | |
} | |
int gi() { | |
int x; | |
while (true) { | |
try { | |
while (_inp.peek() == ',' || _inp.peek() == ' ') | |
_inp.ignore(); | |
if (_inp >> x) | |
return x; | |
else throw 6; | |
} catch (...) { | |
getline(cin, _inps); | |
_inp.clear(); | |
_inp.str(_inps); | |
} | |
} | |
} | |
} | |
#define BSET(a, p) ((a) | (1ll << (p))) | |
#define BCHK(a, p) (((a) & (1ll << (p)))>0) | |
#define BXOR(a, p) ((a) ^ (1ll << (p))); | |
#define BREM(a, p) (BCHK(a, p)?(BXOR(a, p)):(a)) | |
#define BSHO(a, N) (bitset<N>(a)) | |
#define fi first | |
#define sc second | |
#define pb push_back | |
#define X first | |
#define Y second | |
#ifdef DEBUG | |
#define dbg(s) {s;} | |
bool debugging = true; | |
#define PRELUDE {common();} | |
#endif | |
#ifndef DEBUG | |
#define dbg(s) | |
bool debugging = false; | |
#define PRELUDE { common(); ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); } | |
#define endl "\n" | |
#endif | |
#define i32 int32_t | |
#define RBTTYPE int | |
#define ordered_set tree<RBTTYPE, null_type, less<RBTTYPE>, rb_tree_tag,tree_order_statistics_node_update> | |
// Ordered set docs: | |
// order_of_key (k) : Number of items strictly smaller than k . | |
// find_by_order(k) : K-th element in a set (counting from zero). | |
#define all(v) (v).begin(),(v).end() | |
using namespace io; | |
using namespace basics; | |
const int maxn = int(1e6 + 7); | |
const ll inf = ll(1e16 + 7); | |
const ld eps = 1e-7; | |
const ld pi = acosl(-1.0); | |
void hld_print(int, bool); | |
void start(); | |
void finish(); | |
void show_seg(vector<tuple<int,int,int>>); | |
vector < int > G[maxn]; | |
int index_in_chain[maxn]; | |
vector < int > chains[maxn]; | |
int parent[maxn]; | |
int sz[maxn]; | |
int color[maxn]; | |
int ht[maxn]; | |
int max_ht; | |
/* void dfs_fns(int x, int pi, int h) { */ | |
/* parent[x] = pi; */ | |
/* sz[x] = 1; */ | |
/* ht[x] = h; */ | |
/* max_ht = max(max_ht, h); */ | |
/* for (int y : G[x]) { */ | |
/* if (y == pi) continue; */ | |
/* dfs_fns(y, x, h + 1); */ | |
/* sz[x] += sz[y]; */ | |
/* } */ | |
/* } */ | |
void dfs_fns(int x, int pi, int h) { | |
parent[x] = pi; | |
sz[x] = 1; | |
ht[x] = h; | |
max_ht = max(max_ht, h); | |
for (int y : G[x]) { | |
if (y == pi) continue; | |
dfs_fns(y, x, h + 1); | |
sz[x] += sz[y]; | |
} | |
} | |
/* void dfs_hld(int x, int pi) { */ | |
/* int best = -1; */ | |
/* for (int y : G[x]) { */ | |
/* if (y == pi) continue; */ | |
/* if (best < 0 || sz[y] > sz[best]) { */ | |
/* best = y; */ | |
/* } */ | |
/* } */ | |
/* if (best < 0) return; */ | |
/* color[best] = color[x]; */ | |
/* index_in_chain[best] = index_in_chain[x] + 1; */ | |
/* chains[color[x]].pb(best); */ | |
/* dfs_hld(best, x); */ | |
/* for (int y : G[x]) { */ | |
/* if (y == pi || y == best) continue; */ | |
/* color[y] = y; */ | |
/* index_in_chain[y] = 1; */ | |
/* chains[y].pb(y); */ | |
/* dfs_hld(y, x); */ | |
/* } */ | |
/* } */ | |
void dfs_hld(int x, int pi) { | |
int best = -1; | |
for (int y : G[x]) { | |
if (y == pi) continue; | |
if (best < 0 || sz[y] > sz[best]) { | |
best = y; | |
} | |
} | |
if (best < 0) return; | |
color[best] = color[x]; | |
index_in_chain[best] = index_in_chain[x] + 1; | |
chains[color[x]].pb(best); | |
dfs_hld(best, x); | |
for (int y : G[x]) { | |
if (y == pi || y == best) continue; | |
color[y] = y; | |
index_in_chain[y] = 1; | |
chains[y].pb(y); | |
dfs_hld(y, x); | |
} | |
} | |
/* int clk = 0; */ | |
// all(x) = x.begin(), x.end() | |
/* vector < tuple<int, int, int> > segments(int x, int y) { */ | |
/* vector < tuple<int, int, int> > xseg = {}; */ | |
/* vector < tuple<int, int, int> > yseg = {}; */ | |
/* while (true) { */ | |
/* cerr << x << ", " << y << endl; */ | |
/* if (color[x] == color[y]) { */ | |
/* xseg.pb({color[x], index_in_chain[x], index_in_chain[y]}); */ | |
/* break; */ | |
/* } */ | |
/* if (ht[color[x]] < ht[color[y]]) { */ | |
/* yseg.pb({color[y], 1, index_in_chain[y]}); */ | |
/* yseg.pb({-1, parent[color[y]], color[y]}); */ | |
/* y = parent[color[y]]; */ | |
/* } else { */ | |
/* xseg.pb({color[x], index_in_chain[x], 1}); */ | |
/* xseg.pb({-1, color[x], parent[color[x]]}); */ | |
/* x = parent[color[x]]; */ | |
/* } */ | |
/* } */ | |
/* reverse(all(yseg)); */ | |
/* for (auto z : yseg) xseg.pb(z); */ | |
/* return xseg; */ | |
/* } */ | |
// | |
// convention: {c, i, j}, {-1, u, v} | |
vector < tuple<int, int, int> > segments (int x, int y) { | |
vector < tuple < int, int, int> > xseg = {}; | |
vector < tuple < int, int, int> > yseg = {}; | |
while (true) { | |
if (color[x] == color[y]) { | |
xseg.pb({color[x], index_in_chain[x], index_in_chain[y]}); | |
break; | |
} | |
if (ht[color[x]] < ht[color[y]]) { | |
yseg.pb({color[y], 1, index_in_chain[y]}); // go to top of chain | |
yseg.pb({-1, parent[color[y]], color[y]}); | |
y = parent[color[y]]; | |
} else { | |
xseg.pb({color[x], index_in_chain[x], 1}); | |
xseg.pb({-1, color[x], parent[color[x]]}); | |
x = parent[color[x]]; | |
} | |
} | |
reverse(all(yseg)); | |
for (auto z : yseg) xseg.pb(z); | |
return xseg; | |
} | |
/* void dfs_order(int x, int pi) { */ | |
/* clk++; */ | |
/* lft[x] = clk; */ | |
/* for (int y : G[x]) { */ | |
/* if (y == pi) continue; */ | |
/* dfs_order(y, x); */ | |
/* } */ | |
/* rgt[x] = clk; */ | |
/* } */ | |
int clk = 0; | |
int lft[maxn]; | |
int rgt[maxn]; | |
void dfs_order (int x, int pi) { | |
clk++; | |
lft[x] = clk; | |
for (int y : G[x]) { | |
if (y == pi) continue; | |
dfs_order(y, x); | |
} | |
rgt[x] = clk; | |
} | |
int rand_bias(int); // ignore this function | |
void _main() { | |
int n; cin >> n; | |
for (int i = 2; i <= n; i++) { | |
G[rand_bias(i)].pb(i); | |
} | |
/* dfs_order(1, -1); */ | |
dfs_fns(1, -1, 0); | |
// initialize chains | |
color[1] = 1; | |
index_in_chain[1] = 1; | |
chains[1].pb(1); | |
// compute HLD | |
dfs_hld(1, -1); | |
#define SEG | |
#ifdef SEG | |
int a, b; cin >> a >> b; | |
vector < tuple < int, int, int > > seg = segments(a, b); | |
#endif | |
// ignore after this | |
start(); | |
hld_print(n, false); | |
#ifdef SEG | |
show_seg(seg); | |
#endif | |
finish(); | |
} | |
int rand_bias(int x) { | |
return ri(x - 1) + 1; | |
} | |
i32 main() { | |
PRELUDE; | |
auto start = chrono::high_resolution_clock::now(); | |
_main(); | |
auto end = chrono::high_resolution_clock::now(); | |
auto dur = chrono::duration_cast<chrono::milliseconds>(end - start); | |
if (debugging) { | |
/* cout << "Time: " << dur.count() << " ms" << endl; */ | |
} | |
} | |
////////////////// IGNORE //////////////////////// | |
void OUT(string s) { | |
cout << s << endl; | |
} | |
string gradient(double s) { | |
/* return "black"; */ | |
s = 0.95 * s + 0.02; | |
s = 1 - s; | |
int b = floor(s * s * 156) + 100, g = floor(s / 2 * 156 + 100), r = floor((1 - s) * 156 + 100); | |
return fmt::format("#{:x}{:x}{:x}", r, g, b); | |
} | |
string rand_color() { | |
int r = ri(156) + 100, g = ri(156) + 100, b = ri(156) + 100; | |
return fmt::format("#{:x}{:x}{:x}", r, g, b); | |
} | |
void start() { | |
OUT("digraph {"); | |
} | |
void finish() { | |
OUT ("}"); | |
} | |
void hld_print(int n, bool colht) { | |
int* content = sz; | |
int* grad = lft; int max_grad = n; | |
map<int, string> gencolors; | |
for (int i = 1; i <= n; i++) { | |
int col = color[i]; | |
if (gencolors.count(col) == 0) { | |
gencolors[col] = rand_color(); | |
} | |
OUT(fmt::format("v{0} [label=\"{0} ({1}) \", fillcolor=\"{2}\", color = \"{3}\", style=filled, shape = circle, penwidth = 1 ];", | |
to_string(i), | |
colht ? to_string(lft[i]) : to_string(content[i]), | |
colht ? gradient(1.0 * grad[i] / max_grad) : gencolors[col], | |
colht ? gencolors[col] : gradient(1.0 * grad[i] / max_grad) | |
)); | |
} | |
for (int i = 1; i <= n; i++) { | |
for (int y : G[i]) { | |
OUT(fmt::format("v{0} -> v{1}[color = \"{2}\", penwidth={3}];", | |
to_string(i), to_string(y), | |
(color[i] == color[y]) ? gencolors[color[i]] : "#AAAAAA", | |
(color[i] == color[y]) ? "5" : "2")); | |
} | |
} | |
} | |
void show_seg (vector <tuple<int, int, int> > seg) { | |
for (auto z : seg) { | |
int c, x, y; tie(c, x, y) = z; | |
cerr << c << ", " << x << " -- " << y << endl; | |
if (c >= 0) x = chains[c][x - 1], y = chains[c][y - 1]; | |
OUT(fmt::format("v{0} -> v{1}[color=black, penwidth = 6];", to_string(x), to_string(y))); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
compile: | |
pkg-config fmt | |
g++ --std=c++17 code.cc -lfmt | |
run: compile | |
./a.out > out.dot | |
dot -Tpng -Nfontname=Google\ Sans out.dot > out.png | |
disp: | |
firefox out.png |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment