From a9bc65e2c871db1d786f718f6e92ad3921006fdb Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Sat, 5 Sep 2020 17:17:25 -0500 Subject: Update union-find_disjoint_set.cpp --- Data Structures/union-find_disjoint_set.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/Data Structures/union-find_disjoint_set.cpp b/Data Structures/union-find_disjoint_set.cpp index b47139f..0ffee07 100644 --- a/Data Structures/union-find_disjoint_set.cpp +++ b/Data Structures/union-find_disjoint_set.cpp @@ -2,9 +2,9 @@ class UFDS { private: vector p, rank; public: UFDS(int N) { - p.assign(N + 1, 0); + p.assign(N+1, 0); for (int i = 0; i <= N; i++) p[i] = i; - rank.assign(N + 1, 0); + rank.assign(N+1, 0); } int find_set(int i) { return (p[i] == i) ? i : (p[i] = find_set(p[i])); } bool same_set(int i, int j) { return find_set(i) == find_set(j); } @@ -14,4 +14,4 @@ public: rank[x] > rank[y] ? p[y] = x : p[x] = y; if (rank[x] == rank[y]) rank[y]++; } -}; \ No newline at end of file +}; -- cgit v1.2.3-70-g09d2 From fc0be861435ff31084adc65e2070d86ae802de08 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Sun, 6 Sep 2020 10:27:17 -0500 Subject: Changed structs to namespaces --- Graph/centroid.cpp | 2 +- Graph/lca.cpp | 5 ++++- Graph/tarjan_scc.cpp | 2 +- 3 files changed, 6 insertions(+), 3 deletions(-) diff --git a/Graph/centroid.cpp b/Graph/centroid.cpp index 0497bf6..32d5a19 100644 --- a/Graph/centroid.cpp +++ b/Graph/centroid.cpp @@ -1,4 +1,4 @@ -struct centroid { +namespace centroid { int sz[MN], cpar[MN]; bitset vis; void dfs(vector * G, int u, int p = 0) { diff --git a/Graph/lca.cpp b/Graph/lca.cpp index d02598f..2dcd05b 100644 --- a/Graph/lca.cpp +++ b/Graph/lca.cpp @@ -1,4 +1,4 @@ -struct lca { +namespace lca { int d[MN], L[MN][20]; void dfs(vector * G, int u = 1, int p = 0) { d[u] = d[p] + 1, L[u][0] = p; @@ -12,4 +12,7 @@ struct lca { for (int i = 18; i >= 0; i--) if (L[u][i] && L[u][i] != L[v][i]) u = L[u][i], v = L[v][i]; return L[u][0]; } + inline int dist(vector * G, int u, int v) { + return d[u]+d[v]-2*lca(G, u, v); + } } diff --git a/Graph/tarjan_scc.cpp b/Graph/tarjan_scc.cpp index 7f89859..f5b8d35 100644 --- a/Graph/tarjan_scc.cpp +++ b/Graph/tarjan_scc.cpp @@ -1,4 +1,4 @@ -struct tarjan { +namespace tarjan { int cnt, scc_num, scc[MN], in[MN], low[MN]; stack s; bitset ins; -- cgit v1.2.3-70-g09d2 From dcb2b2d3768f6467e68d285b48525ece51fd13ac Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Sun, 6 Sep 2020 10:59:36 -0500 Subject: Fixed a few things in lca.cpp --- Graph/lca.cpp | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/Graph/lca.cpp b/Graph/lca.cpp index 2dcd05b..bba90aa 100644 --- a/Graph/lca.cpp +++ b/Graph/lca.cpp @@ -7,12 +7,12 @@ namespace lca { } int lca(vector * G, int u, int v) { if (d[u] > d[v]) swap(u, v); - for (int i = 18; i >= 0; i--) if (d[v] - (1 << i) >= d[u]) v = L[v][i]; + for (int i = 18; i >= 0; --i) if (d[v] - (1 << i) >= d[u]) v = L[v][i]; if (u == v) return u; - for (int i = 18; i >= 0; i--) if (L[u][i] && L[u][i] != L[v][i]) u = L[u][i], v = L[v][i]; + for (int i = 18; i >= 0; --i) if (L[u][i] && L[u][i] != L[v][i]) u = L[u][i], v = L[v][i]; return L[u][0]; } inline int dist(vector * G, int u, int v) { - return d[u]+d[v]-2*lca(G, u, v); + return d[u]+d[v]-2*d[lca(G, u, v)]; } } -- cgit v1.2.3-70-g09d2 From f79db8f69575229c7bb21c00f7d7ced120d0e187 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Sun, 6 Sep 2020 14:27:14 -0500 Subject: New style --- Data Structures/dynamic_segment_tree_2d.cpp | 8 ++++---- Data Structures/seg_fenwick_tree.cpp | 2 +- Data Structures/seg_ordered_set_tree.cpp | 8 ++++---- Data Structures/segment_tree.cpp | 2 +- Graph/centroid.cpp | 4 ++-- Graph/lca.cpp | 2 +- Graph/tarjan_scc.cpp | 4 ++-- Math/numtheory.cpp | 2 +- 8 files changed, 16 insertions(+), 16 deletions(-) diff --git a/Data Structures/dynamic_segment_tree_2d.cpp b/Data Structures/dynamic_segment_tree_2d.cpp index 6948421..fe81b97 100644 --- a/Data Structures/dynamic_segment_tree_2d.cpp +++ b/Data Structures/dynamic_segment_tree_2d.cpp @@ -3,7 +3,7 @@ struct y_node { y_node* c[2]; y_node() { val = 0; c[0] = c[1] = 0; } y_node* get_c(int i) { return (!c[i] ? c[i] = new y_node : c[i]); } - void update(int y, int v, int l = -1, int r = MN) { + void update(int y, int v, int l = -1, int r = MX) { if (l == r) val += v; else { int m = (l + r) >> 1; @@ -11,7 +11,7 @@ struct y_node { val = (c[0] ? c[0]->val : 0) + (c[1] ? c[1]->val : 0); } } - int query(int yl, int yr, int l = -1, int r = MN) { + int query(int yl, int yr, int l = -1, int r = MX) { if (yl > r || yr < l) return 0; if (yl <= l && yr >= r) return val; int m = (l + r) >> 1; @@ -24,7 +24,7 @@ struct x_node { x_node* c[2]; x_node() { c[0] = c[1] = 0;} x_node* get_c(int i) { return (!c[i] ? c[i] = new x_node : c[i]); } - void update(int x, int y, int v, int l = -1, int r = MN) { + void update(int x, int y, int v, int l = -1, int r = MX) { if (l == r) seg.update(y, v); else { int m = (l + r) >> 1; @@ -32,7 +32,7 @@ struct x_node { seg.update(y, (c[0] ? c[0]->seg.query(y, y) : 0) + (c[1] ? c[1]->seg.query(y, y) : 0)); } } - int query(int xl, int xr, int yl, int yr, int l = -1, int r = MN) { + int query(int xl, int xr, int yl, int yr, int l = -1, int r = MX) { if (xl > r || xr < l) return 0; if (xl <= l && xr >= r) return seg.query(yl, yr); int m = (l + r) >> 1; diff --git a/Data Structures/seg_fenwick_tree.cpp b/Data Structures/seg_fenwick_tree.cpp index b3dae30..d0b7066 100644 --- a/Data Structures/seg_fenwick_tree.cpp +++ b/Data Structures/seg_fenwick_tree.cpp @@ -22,7 +22,7 @@ struct node { int m = (l + r) >> 1; return (c[0] ? c[0]->query(a, b, l, m) : 0) + (c[1] ? c[1]->query(a, b, m + 1, r) : 0); } -} FT[MN]; +} FT[MX]; void update(int x, int y, int v) { for (; x < N; x += x & -x) FT[x].update(y, v); } int query(int x, int y1, int y2) { int ret = 0; for (; x > 0; x -= x & -x) ret += FT[x].query(y1, y2); return ret; } diff --git a/Data Structures/seg_ordered_set_tree.cpp b/Data Structures/seg_ordered_set_tree.cpp index 2a11ee8..efc5815 100644 --- a/Data Structures/seg_ordered_set_tree.cpp +++ b/Data Structures/seg_ordered_set_tree.cpp @@ -3,11 +3,11 @@ using namespace std; using namespace __gnu_pbds; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; -constexpr int MN = MN; +constexpr int MX = MX; -ordered_set S[4 * MN]; +ordered_set S[4 * MX]; -void update(int x, int y, int l = 0, int r = MN, int n = 1) { +void update(int x, int y, int l = 0, int r = MX, int n = 1) { if (l != r) { int m = (l + r) >> 1; x <= m ? update(x, y, l, m, n << 1) : update(x, y, m + 1, r, n << 1 | 1); @@ -15,7 +15,7 @@ void update(int x, int y, int l = 0, int r = MN, int n = 1) { S[n].insert(y); } -int query(int xl, int xr, int yl, int yr, int l = 0, int r = MN, int n = 1) { +int query(int xl, int xr, int yl, int yr, int l = 0, int r = MX, int n = 1) { if (l > r || l > xr || r < xl) return 0; if (l >= xl && r <= xr) return S[n].order_of_key(yr + 1) - S[n].order_of_key(yl); else { diff --git a/Data Structures/segment_tree.cpp b/Data Structures/segment_tree.cpp index a2b1d40..1d74f2c 100644 --- a/Data Structures/segment_tree.cpp +++ b/Data Structures/segment_tree.cpp @@ -1,5 +1,5 @@ template struct seg_tree { - T seg[4*MN], tmp[4*MN]; + T seg[4*MX], tmp[4*MX]; inline T pull(const T & a, const T & b) { return a+b; } inline void push(int l, int r, int n) { seg[n] += (r-l+1)*tmp[n]; diff --git a/Graph/centroid.cpp b/Graph/centroid.cpp index 32d5a19..4dd5ac1 100644 --- a/Graph/centroid.cpp +++ b/Graph/centroid.cpp @@ -1,6 +1,6 @@ namespace centroid { - int sz[MN], cpar[MN]; - bitset vis; + int sz[MX], cpar[MX]; + bitset vis; void dfs(vector * G, int u, int p = 0) { sz[u] = 1; for (int v : G[u]) if (v != p && !vis[v]) dfs(G, v, u), sz[u] += sz[v]; diff --git a/Graph/lca.cpp b/Graph/lca.cpp index bba90aa..38d972e 100644 --- a/Graph/lca.cpp +++ b/Graph/lca.cpp @@ -1,5 +1,5 @@ namespace lca { - int d[MN], L[MN][20]; + int d[MX], L[MX][20]; void dfs(vector * G, int u = 1, int p = 0) { d[u] = d[p] + 1, L[u][0] = p; for (int i = 0; i < 18 && L[u][i]; i++) L[u][i + 1] = L[L[u][i]][i]; diff --git a/Graph/tarjan_scc.cpp b/Graph/tarjan_scc.cpp index f5b8d35..a9bad2e 100644 --- a/Graph/tarjan_scc.cpp +++ b/Graph/tarjan_scc.cpp @@ -1,7 +1,7 @@ namespace tarjan { - int cnt, scc_num, scc[MN], in[MN], low[MN]; + int cnt, scc_num, scc[MX], in[MX], low[MX]; stack s; - bitset ins; + bitset ins; void tarjan(vector * G, int u) { low[u] = in[u] = cnt++, ins[u] = 1; s.push(u); for (int v : G[u]) { diff --git a/Math/numtheory.cpp b/Math/numtheory.cpp index 02228e2..a019b05 100644 --- a/Math/numtheory.cpp +++ b/Math/numtheory.cpp @@ -11,7 +11,7 @@ inline ll pw(ll base, ll exp) { inline ll inv(ll x) { return pw(x, MOD-2); } -ll fact[MN] = { 1 }, ifact[MN] = { 1 }; +ll fact[MX] = { 1 }, ifact[MX] = { 1 }; inline ll nCr(int n, int k) { return fact[n]*ifact[k]%MOD*ifact[n-k]%MOD; } -- cgit v1.2.3-70-g09d2 From 7836b0c0ba58e3b68dd937e042e7c62e687455f7 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Sun, 6 Sep 2020 17:54:27 -0500 Subject: Update segment_tree.cpp --- Data Structures/segment_tree.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/Data Structures/segment_tree.cpp b/Data Structures/segment_tree.cpp index 1d74f2c..c0f317b 100644 --- a/Data Structures/segment_tree.cpp +++ b/Data Structures/segment_tree.cpp @@ -11,7 +11,7 @@ template struct seg_tree { if (l == r) seg[n] = v; else { int m = (l+r)>>1; - build(l, m, n<<1), build(m+1, r, n<<1|1); + build(v, l, m, n<<1), build(v, m+1, r, n<<1|1); seg[n] = pull(seg[n<<1], seg[n<<1|1]); } } -- cgit v1.2.3-70-g09d2 From 105787a83793986c10c8c6ac622eae41f7dc3f64 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 8 Sep 2020 15:32:49 -0500 Subject: Modified templates --- Template/template.cpp | 3 ++- Template/usaco.cpp | 3 ++- 2 files changed, 4 insertions(+), 2 deletions(-) diff --git a/Template/template.cpp b/Template/template.cpp index 80b2748..48856fd 100644 --- a/Template/template.cpp +++ b/Template/template.cpp @@ -21,7 +21,8 @@ using vi = vector; using vl = vector; using vd = vector; using vii = vector; using vpl = vector; using vpd = vector; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using ordered_multiset = tree, rb_tree_tag, tree_order_statistics_node_update>; // Use with caution -constexpr int INF = 1e9; constexpr ll LINF = 1e18; constexpr ll MOD = 1e9+7; constexpr ld PI = 4*atan((ld)1); +constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7; +constexpr ld PI = 4*atan((ld)1); int main() { if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); diff --git a/Template/usaco.cpp b/Template/usaco.cpp index f730b4c..6f46a75 100644 --- a/Template/usaco.cpp +++ b/Template/usaco.cpp @@ -21,7 +21,8 @@ using vi = vector; using vl = vector; using vd = vector; using vii = vector; using vpl = vector; using vpd = vector; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using ordered_multiset = tree, rb_tree_tag, tree_order_statistics_node_update>; // Use with caution -constexpr int INF = 1e9; constexpr ll LINF = 1e18; constexpr ll MOD = 1e9+7; constexpr ld PI = 4*atan((ld)1); +constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7; +constexpr ld PI = 4*atan((ld)1); void io(const str & s) { if (fopen((s+".in").c_str(), "r")) freopen((s+".in").c_str(), "r", stdin), freopen((s+".out").c_str(), "w", stdout); ios_base::sync_with_stdio(0), cin.tie(0); -- cgit v1.2.3-70-g09d2 From 2c24b07ac65bfee2a1c41ead0bbc13c0730517ac Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 8 Sep 2020 16:42:40 -0500 Subject: Update fenwick_tree.cpp --- Data Structures/fenwick_tree.cpp | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) diff --git a/Data Structures/fenwick_tree.cpp b/Data Structures/fenwick_tree.cpp index ba75c58..4f73507 100644 --- a/Data Structures/fenwick_tree.cpp +++ b/Data Structures/fenwick_tree.cpp @@ -1,8 +1,9 @@ template class fenwick_tree { -private: vector FT; +private: int N; T FT[MX]; public: - fenwick_tree(int N) { FT.assign(N + 5, 0); } - void update(int x, T val) { if (++x) for (; x < FT.size(); x += x & -x) FT[x] += val; } - T query(int x) { T ret = 0; if (++x) for (; x; x -= x & -x) ret += FT[x]; return ret; } - T query(int x, int y) { return query(y) - query(x - 1); } -}; \ No newline at end of file + fenwick_tree(int n) { N = n } + fenwick_tree(int n, T A[]) { N = n; memcpy(FT, A, sizeof FT); } + void update(int x, T val) { if (++x) for (; x < N; x += x&-x) FT[x] += val; } + T query(int x) { T ret = 0; if (++x) for (; x; x -= x&-x) ret += FT[x]; return ret; } + T query(int x, int y) { return query(y)-query(x-1); } +}; -- cgit v1.2.3-70-g09d2 From 3ee05dc851cae4e0ea941c940c27597e83bcb620 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 8 Sep 2020 22:06:09 -0500 Subject: Added builtins to templates --- Template/template.cpp | 3 +++ Template/usaco.cpp | 3 +++ 2 files changed, 6 insertions(+) diff --git a/Template/template.cpp b/Template/template.cpp index 48856fd..6553f13 100644 --- a/Template/template.cpp +++ b/Template/template.cpp @@ -14,6 +14,9 @@ #define all(x) begin(x), end(x) #define tr(a, x) for (auto& a : x) #define mem(a, b) memset(a, (b), sizeof(a)) +#define pc __builtin_popcount +#define clz __builtin_clz +#define ctz __builtin_ctz using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; using str = string; using ll = long long; using ld = long double; using cd = complex; using ii = pair; using pl = pair; using pd = pair; diff --git a/Template/usaco.cpp b/Template/usaco.cpp index 6f46a75..edab30f 100644 --- a/Template/usaco.cpp +++ b/Template/usaco.cpp @@ -14,6 +14,9 @@ #define all(x) begin(x), end(x) #define tr(a, x) for (auto& a : x) #define mem(a, b) memset(a, (b), sizeof(a)) +#define pc __builtin_popcount +#define clz __builtin_clz +#define ctz __builtin_ctz using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; using str = string; using ll = long long; using ld = long double; using cd = complex; using ii = pair; using pl = pair; using pd = pair; -- cgit v1.2.3-70-g09d2 From 0c674144e9cd4bef9e56481a89c8121d298f29fa Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 8 Sep 2020 22:27:18 -0500 Subject: Consistent style --- Template/template.cpp | 2 +- Template/usaco.cpp | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/Template/template.cpp b/Template/template.cpp index 6553f13..5d94c8f 100644 --- a/Template/template.cpp +++ b/Template/template.cpp @@ -12,7 +12,7 @@ #define rsz resize #define sz(x) (int)x.size() #define all(x) begin(x), end(x) -#define tr(a, x) for (auto& a : x) +#define tr(a, x) for (auto & a : x) #define mem(a, b) memset(a, (b), sizeof(a)) #define pc __builtin_popcount #define clz __builtin_clz diff --git a/Template/usaco.cpp b/Template/usaco.cpp index edab30f..5f82d7e 100644 --- a/Template/usaco.cpp +++ b/Template/usaco.cpp @@ -12,7 +12,7 @@ #define rsz resize #define sz(x) (int)x.size() #define all(x) begin(x), end(x) -#define tr(a, x) for (auto& a : x) +#define tr(a, x) for (auto & a : x) #define mem(a, b) memset(a, (b), sizeof(a)) #define pc __builtin_popcount #define clz __builtin_clz -- cgit v1.2.3-70-g09d2 From 6f849c97711b88160e4c4c959b32f9d7becf396b Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Wed, 9 Sep 2020 17:13:35 -0500 Subject: Update templates --- Template/template.cpp | 2 +- Template/usaco.cpp | 9 +++------ 2 files changed, 4 insertions(+), 7 deletions(-) diff --git a/Template/template.cpp b/Template/template.cpp index 5d94c8f..df2e7ee 100644 --- a/Template/template.cpp +++ b/Template/template.cpp @@ -24,8 +24,8 @@ using vi = vector; using vl = vector; using vd = vector; using vii = vector; using vpl = vector; using vpd = vector; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using ordered_multiset = tree, rb_tree_tag, tree_order_statistics_node_update>; // Use with caution -constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7; constexpr ld PI = 4*atan((ld)1); +constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7; int main() { if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout); diff --git a/Template/usaco.cpp b/Template/usaco.cpp index 5f82d7e..9584afc 100644 --- a/Template/usaco.cpp +++ b/Template/usaco.cpp @@ -24,15 +24,12 @@ using vi = vector; using vl = vector; using vd = vector; using vii = vector; using vpl = vector; using vpd = vector; template using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using ordered_multiset = tree, rb_tree_tag, tree_order_statistics_node_update>; // Use with caution -constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7; constexpr ld PI = 4*atan((ld)1); -void io(const str & s) { - if (fopen((s+".in").c_str(), "r")) freopen((s+".in").c_str(), "r", stdin), freopen((s+".out").c_str(), "w", stdout); - ios_base::sync_with_stdio(0), cin.tie(0); -} +constexpr ll MX = 1e5+5, ll INF = 1e9, LINF = 1e18, ll MOD = 1e9+7; int main() { - io("name"); + ifstream cin("in"); ofstream cout("in"); + ios_base::sync_with_stdio(0), cin.tie(0); -- cgit v1.2.3-70-g09d2 From 62c0639f0c1319f0d1758be6942a48f66a829256 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Mon, 14 Sep 2020 10:27:55 -0500 Subject: Delete util.cpp --- Miscellaneous/util.cpp | 7 ------- 1 file changed, 7 deletions(-) delete mode 100644 Miscellaneous/util.cpp diff --git a/Miscellaneous/util.cpp b/Miscellaneous/util.cpp deleted file mode 100644 index 2816c2b..0000000 --- a/Miscellaneous/util.cpp +++ /dev/null @@ -1,7 +0,0 @@ -template // Coordinate compression -void compress(BidirectionalIterator first, BidirectionalIterator last) { - vector> tmp; - for (auto it = first; it != last; ++it) tmp.emplace_back(*it, it-first); - sort(begin(tmp), end(tmp)); - for (auto it = begin(tmp); it != end(tmp); ++it) (first+it->s) = it-begin(tmp); -} -- cgit v1.2.3-70-g09d2 From 38b999de0298946fecd9f8e1539f99c22190d052 Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 15 Sep 2020 14:41:14 -0500 Subject: Update numtheory.cpp --- Math/numtheory.cpp | 1 - 1 file changed, 1 deletion(-) diff --git a/Math/numtheory.cpp b/Math/numtheory.cpp index a019b05..b211282 100644 --- a/Math/numtheory.cpp +++ b/Math/numtheory.cpp @@ -8,7 +8,6 @@ inline ll pw(ll base, ll exp) { } return res; } - inline ll inv(ll x) { return pw(x, MOD-2); } ll fact[MX] = { 1 }, ifact[MX] = { 1 }; -- cgit v1.2.3-70-g09d2