diff options
Diffstat (limited to 'content/graph')
28 files changed, 108 insertions, 106 deletions
diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp index e391948..22a9082 100644 --- a/content/graph/LCA_sparse.cpp +++ b/content/graph/LCA_sparse.cpp @@ -5,9 +5,9 @@ struct LCA { SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector<vector<int>>& adj, int root) { - depth.assign(2 * sz(adj), 0); - visited.assign(2 * sz(adj), -1); - first.assign(sz(adj), 2 * sz(adj)); + depth.assign(2 * ssize(adj), 0); + visited.assign(2 * ssize(adj), -1); + first.assign(ssize(adj), 2 * ssize(adj)); idx = 0; dfs(adj, root); st.init(depth); @@ -18,7 +18,7 @@ struct LCA { first[v] = min(idx, first[v]), idx++; for (int u : adj[v]) { - if (first[u] == 2 * sz(adj)) { + if (first[u] == 2 * ssize(adj)) { dfs(adj, u, d + 1); visited[idx] = v, depth[idx] = d, idx++; }}} diff --git a/content/graph/TSP.cpp b/content/graph/TSP.cpp index 6223858..4d2479c 100644 --- a/content/graph/TSP.cpp +++ b/content/graph/TSP.cpp @@ -1,7 +1,7 @@ vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten. auto TSP() { - int n = sz(dist), m = 1 << n; + int n = ssize(dist), m = 1 << n; vector<vector<edge>> dp(n, vector<edge>(m, edge{INF, -1})); for (int c = 0; c < n; c++) @@ -21,7 +21,7 @@ auto TSP() { vector<int> tour = {0}; int v = 0; - while (tour.back() != 0 || sz(tour) == 1) + while (tour.back() != 0 || ssize(tour) == 1) tour.push_back(dp[tour.back()] [(v |= (1 << tour.back()))].to); // Enthält Knoten 0 zweimal. An erster und letzter Position. diff --git a/content/graph/articulationPoints.cpp b/content/graph/articulationPoints.cpp index 25ff67e..60970e6 100644 --- a/content/graph/articulationPoints.cpp +++ b/content/graph/articulationPoints.cpp @@ -14,14 +14,14 @@ int dfs(int v, int from = -1) { if (num[e.to] < me) st.push_back(e); } else { if (v == root) rootCount++; - int si = sz(st); + int si = ssize(st); int up = dfs(e.to, e.id); top = min(top, up); if (up >= me) isArt[v] = true; if (up > me) bridges.push_back(e); if (up <= me) st.push_back(e); if (up == me) { - bcc.emplace_back(si + all(st)); + bcc.emplace_back(begin(st) + si, end(st)); st.resize(si); }}} return top; @@ -29,12 +29,12 @@ int dfs(int v, int from = -1) { void find() { counter = 0; - num.assign(sz(adj), 0); - isArt.assign(sz(adj), false); + num.assign(ssize(adj), 0); + isArt.assign(ssize(adj), false); bridges.clear(); st.clear(); bcc.clear(); - for (int v = 0; v < sz(adj); v++) { + for (int v = 0; v < ssize(adj); v++) { if (!num[v]) { root = v; rootCount = 0; diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp index a6f4c6e..eeff156 100644 --- a/content/graph/bitonicTSP.cpp +++ b/content/graph/bitonicTSP.cpp @@ -1,10 +1,10 @@ vector<vector<double>> dist; // Initialisiere mit Entfernungen zwischen Punkten. auto bitonicTSP() { - vector<double> dp(sz(dist), HUGE_VAL); - vector<int> pre(sz(dist)); // nur für Tour + vector<double> dp(ssize(dist), HUGE_VAL); + vector<int> pre(ssize(dist)); // nur für Tour dp[0] = 0; dp[1] = 2 * dist[0][1]; pre[1] = 0; - for (unsigned int i = 2; i < sz(dist); i++) { + for (unsigned int i = 2; i < ssize(dist); i++) { double link = 0; for (int j = i - 2; j >= 0; j--) { link += dist[j + 1][j + 2]; @@ -15,7 +15,7 @@ auto bitonicTSP() { }}} // return dp.back(); // Länge der Tour - int j, n = sz(dist) - 1; + int j, n = ssize(dist) - 1; vector<int> ut, lt = {n, n - 1}; do { j = pre[n]; @@ -25,7 +25,7 @@ auto bitonicTSP() { } } while(n = j + 1, j > 0); (lt.back() == 1 ? lt : ut).push_back(0); - reverse(all(lt)); - lt.insert(lt.end(), all(ut)); + ranges::reverse(lt); + lt.insert(end(lt), begin(ut), end(ut)); return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position. } diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp index cacfb9c..b6d72d8 100644 --- a/content/graph/bitonicTSPsimple.cpp +++ b/content/graph/bitonicTSPsimple.cpp @@ -3,7 +3,7 @@ vector<vector<double>> dp; double get(int p1, int p2) { int v = max(p1, p2) + 1; - if (v == sz(dist)) return dist[p1][v - 1] + dist[p2][v - 1]; + if (v == ssize(dist)) return dist[p1][v - 1] + dist[p2][v - 1]; if (dp[p1][p2] >= 0.0) return dp[p1][p2]; double tryLR = dist[p1][v] + get(v, p2); double tryRL = dist[p2][v] + get(p1, v); @@ -11,17 +11,19 @@ double get(int p1, int p2) { } auto bitonicTSP() { - dp = vector<vector<double>>(sz(dist), - vector<double>(sz(dist), -1)); + dp = vector<vector<double>>(ssize(dist), + vector<double>(ssize(dist), -1)); get(0, 0); - // return dp[0][0]; // Länger der Tour + // return dp[0][0]; // Länge der Tour vector<int> lr = {0}, rl = {0}; - for (int p1 = 0, p2 = 0, v; (v = max(p1, p2)+1) < sz(dist);) { + for (int p1 = 0, p2 = 0, v; + (v = max(p1, p2)+1) < ssize(dist);) { if (dp[p1][p2] == dist[p1][v] + dp[v][p2]) { lr.push_back(v); p1 = v; } else { rl.push_back(v); p2 = v; }} lr.insert(lr.end(), rl.rbegin(), rl.rend()); - return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position. + // Enthält Knoten 0 zweimal. An erster und letzter Position. + return lr; } diff --git a/content/graph/blossom.cpp b/content/graph/blossom.cpp index 7bd494a..3c9bd31 100644 --- a/content/graph/blossom.cpp +++ b/content/graph/blossom.cpp @@ -32,7 +32,7 @@ struct GM { auto h = label[r] = label[s] = {~x, y}; int join; while (true) { - if (s != sz(adj)) swap(r, s); + if (s != ssize(adj)) swap(r, s); r = findFirst(label[pairs[r]].first); if (label[r] == h) { join = r; @@ -48,13 +48,13 @@ struct GM { }}} bool augment(int v) { - label[v] = {sz(adj), -1}; - first[v] = sz(adj); + label[v] = {ssize(adj), -1}; + first[v] = ssize(adj); head = tail = 0; for (que[tail++] = v; head < tail;) { int x = que[head++]; for (int y : adj[x]) { - if (pairs[y] == sz(adj) && y != v) { + if (pairs[y] == ssize(adj) && y != v) { pairs[y] = x; rematch(x, y); return true; @@ -70,12 +70,12 @@ struct GM { int match() { int matching = head = tail = 0; - for (int v = 0; v < sz(adj); v++) { - if (pairs[v] < sz(adj) || !augment(v)) continue; + for (int v = 0; v < ssize(adj); v++) { + if (pairs[v] < ssize(adj) || !augment(v)) continue; matching++; for (int i = 0; i < tail; i++) label[que[i]] = label[pairs[que[i]]] = {-1, -1}; - label[sz(adj)] = {-1, -1}; + label[ssize(adj)] = {-1, -1}; } return matching; } diff --git a/content/graph/bronKerbosch.cpp b/content/graph/bronKerbosch.cpp index 0cfcc5f..cf07c88 100644 --- a/content/graph/bronKerbosch.cpp +++ b/content/graph/bronKerbosch.cpp @@ -11,7 +11,7 @@ void bronKerboschRec(bits R, bits P, bits X) { } else { int q = min(P._Find_first(), X._Find_first()); bits cands = P & ~adj[q]; - for (int i = 0; i < sz(adj); i++) if (cands[i]) { + for (int i = 0; i < ssize(adj); i++) if (cands[i]) { R[i] = 1; bronKerboschRec(R, P & adj[i], X & adj[i]); R[i] = P[i] = 0; @@ -20,5 +20,5 @@ void bronKerboschRec(bits R, bits P, bits X) { void bronKerbosch() { cliques.clear(); - bronKerboschRec({}, {(1ull << sz(adj)) - 1}, {}); + bronKerboschRec({}, {(1ull << ssize(adj)) - 1}, {}); } diff --git a/content/graph/centroid.cpp b/content/graph/centroid.cpp index 820945b..3cd5519 100644 --- a/content/graph/centroid.cpp +++ b/content/graph/centroid.cpp @@ -15,7 +15,7 @@ pair<int, int> dfs_cent(int v, int from, int n) { } pair<int, int> find_centroid(int root = 0) { - s.resize(sz(adj)); + s.resize(ssize(adj)); dfs_sz(root); return dfs_cent(root, -1, s[root]); } diff --git a/content/graph/cycleCounting.cpp b/content/graph/cycleCounting.cpp index 471d399..65bf1a0 100644 --- a/content/graph/cycleCounting.cpp +++ b/content/graph/cycleCounting.cpp @@ -9,8 +9,8 @@ struct cycles { cycles(int n) : adj(n), seen(n), paths(n) {} void addEdge(int u, int v) { - adj[u].push_back({v, sz(edges)}); - adj[v].push_back({u, sz(edges)}); + adj[u].push_back({v, ssize(edges)}); + adj[v].push_back({u, ssize(edges)}); edges.push_back({u, v}); } @@ -38,8 +38,8 @@ struct cycles { bool isCycle(cycle cur) { // cycle must be constrcuted from base if (cur.none()) return false; - init(sz(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ - for (int i = 0; i < sz(edges); i++) { + init(ssize(adj)); // union find @\sourceref{datastructures/unionFind.cpp}@ + for (int i = 0; i < ssize(edges); i++) { if (cur[i]) { cur[i] = false; if (findSet(edges[i].first) == @@ -50,12 +50,12 @@ struct cycles { } int count() { - for (int i = 0; i < sz(adj); i++) findBase(i); - assert(sz(base) < 30); + for (int i = 0; i < ssize(adj); i++) findBase(i); + assert(ssize(base) < 30); int res = 0; - for (int i = 1; i < (1 << sz(base)); i++) { + for (int i = 1; i < (1 << ssize(base)); i++) { cycle cur; - for (int j = 0; j < sz(base); j++) + for (int j = 0; j < ssize(base); j++) if (((i >> j) & 1) != 0) cur ^= base[j]; if (isCycle(cur)) res++; } diff --git a/content/graph/dijkstra.cpp b/content/graph/dijkstra.cpp index 61c636d..4c1c9d8 100644 --- a/content/graph/dijkstra.cpp +++ b/content/graph/dijkstra.cpp @@ -2,8 +2,8 @@ using path = pair<ll, int>; //dist, destination auto dijkstra(const vector<vector<path>>& adj, int start) { priority_queue<path, vector<path>, greater<path>> pq; - vector<ll> dist(sz(adj), INF); - vector<int> prev(sz(adj), -1); + vector<ll> dist(ssize(adj), INF); + vector<int> prev(ssize(adj), -1); dist[start] = 0; pq.emplace(0, start); while (!pq.empty()) { diff --git a/content/graph/dinic.cpp b/content/graph/dinic.cpp index 2e58a2d..c8c34a8 100644 --- a/content/graph/dinic.cpp +++ b/content/graph/dinic.cpp @@ -8,12 +8,12 @@ int s, t; vector<int> pt, dist; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); } bool bfs() { - dist.assign(sz(adj), -1); + dist.assign(ssize(adj), -1); dist[s] = 0; queue<int> q({s}); while (!q.empty() && dist[t] < 0) { @@ -28,7 +28,7 @@ bool bfs() { ll dfs(int v, ll flow = INF) { if (v == t || flow == 0) return flow; - for (; pt[v] < sz(adj[v]); pt[v]++) { + for (; pt[v] < ssize(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; ll cur = dfs(e.to, min(e.c - e.f, flow)); @@ -44,7 +44,7 @@ ll maxFlow(int source, int target) { s = source, t = target; ll flow = 0; while (bfs()) { - pt.assign(sz(adj), 0); + pt.assign(ssize(adj), 0); ll cur; do { cur = dfs(s); diff --git a/content/graph/dinicScaling.cpp b/content/graph/dinicScaling.cpp index 0974b78..0082c05 100644 --- a/content/graph/dinicScaling.cpp +++ b/content/graph/dinicScaling.cpp @@ -8,12 +8,12 @@ int s, t; vector<int> pt, dist; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u]) - 1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u]) - 1, 0, 0}); } bool bfs(ll lim) { - dist.assign(sz(adj), -1); + dist.assign(ssize(adj), -1); dist[s] = 0; queue<int> q({s}); while (!q.empty() && dist[t] < 0) { @@ -28,7 +28,7 @@ bool bfs(ll lim) { ll dfs(int v, ll flow) { if (v == t || flow == 0) return flow; - for (; pt[v] < sz(adj[v]); pt[v]++) { + for (; pt[v] < ssize(adj[v]); pt[v]++) { Edge& e = adj[v][pt[v]]; if (dist[e.to] != dist[v] + 1) continue; ll cur = dfs(e.to, min(e.c - e.f, flow)); @@ -45,7 +45,7 @@ ll maxFlow(int source, int target) { ll flow = 0; for (ll lim = (1LL << 62); lim >= 1; lim /= 2) { while (bfs(lim)) { - pt.assign(sz(adj), 0); + pt.assign(ssize(adj), 0); ll cur; do { cur = dfs(s, lim); diff --git a/content/graph/euler.cpp b/content/graph/euler.cpp index a5ea192..c506d58 100644 --- a/content/graph/euler.cpp +++ b/content/graph/euler.cpp @@ -3,16 +3,16 @@ vector<int> to, validIdx, cycle; vector<bool> used; void addEdge(int u, int v) { - idx[u].push_back(sz(to)); + idx[u].push_back(ssize(to)); to.push_back(v); used.push_back(false); - idx[v].push_back(sz(to)); // für ungerichtet + idx[v].push_back(ssize(to)); // für ungerichtet to.push_back(u); used.push_back(false); } void euler(int v) { // init idx und validIdx - for (;validIdx[v] < sz(idx[v]); validIdx[v]++) { + for (;validIdx[v] < ssize(idx[v]); validIdx[v]++) { if (!used[idx[v][validIdx[v]]]) { int u = to[idx[v][validIdx[v]]]; used[idx[v][validIdx[v]]] = true; diff --git a/content/graph/floydWarshall.cpp b/content/graph/floydWarshall.cpp index df096c2..1a1138d 100644 --- a/content/graph/floydWarshall.cpp +++ b/content/graph/floydWarshall.cpp @@ -2,16 +2,16 @@ vector<vector<ll>> dist; // Entfernung zwischen je zwei Punkten. vector<vector<int>> next; void floydWarshall() { - next.assign(sz(dist), vector<int>(sz(dist), -1)); - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { + next.assign(ssize(dist), vector<int>(ssize(dist), -1)); + for (int i = 0; i < ssize(dist); i++) { + for (int j = 0; j < ssize(dist); j++) { if (dist[i][j] < INF) { next[i][j] = j; }}} - for (int k = 0; k < sz(dist); k++) { - for (int i = 0; i < sz(dist); i++) { - for (int j = 0; j < sz(dist); j++) { + for (int k = 0; k < ssize(dist); k++) { + for (int i = 0; i < ssize(dist); i++) { + for (int j = 0; j < ssize(dist); j++) { // only needed if dist can be negative if (dist[i][k] == INF || dist[k][j] == INF) continue; if (dist[i][j] > dist[i][k] + dist[k][j]) { diff --git a/content/graph/havelHakimi.cpp b/content/graph/havelHakimi.cpp index ac4d67d..9f4c081 100644 --- a/content/graph/havelHakimi.cpp +++ b/content/graph/havelHakimi.cpp @@ -1,12 +1,12 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) { priority_queue<pair<int, int>> pq; - for (int i = 0; i < sz(deg); i++) { + for (int i = 0; i < ssize(deg); i++) { if (deg[i] > 0) pq.push({deg[i], i}); } - vector<vector<int>> adj(sz(deg)); + vector<vector<int>> adj(ssize(deg)); while (!pq.empty()) { auto [degV, v] = pq.top(); pq.pop(); - if (sz(pq) < degV) return {}; //impossible + if (ssize(pq) < degV) return {}; //impossible vector<pair<int, int>> todo(degV); for (auto& e : todo) e = pq.top(), pq.pop(); for (auto [degU, u] : todo) { diff --git a/content/graph/hld.cpp b/content/graph/hld.cpp index 65d3f5c..e365b13 100644 --- a/content/graph/hld.cpp +++ b/content/graph/hld.cpp @@ -21,7 +21,7 @@ void dfs_hld(int v = 0, int from = -1) { } void init(int root = 0) { - int n = sz(adj); + int n = ssize(adj); sz.assign(n, 1), nxt.assign(n, root), par.assign(n, -1); in.resize(n), out.resize(n); counter = 0; diff --git a/content/graph/hopcroftKarp.cpp b/content/graph/hopcroftKarp.cpp index 7c0fec5..d07bd3a 100644 --- a/content/graph/hopcroftKarp.cpp +++ b/content/graph/hopcroftKarp.cpp @@ -21,7 +21,7 @@ bool bfs(int l) { } bool dfs(int v) { - for (; ptr[v] < sz(adj[v]); ptr[v]++) { + for (; ptr[v] < ssize(adj[v]); ptr[v]++) { int u = adj[v][ptr[v]]; if (pairs[u] < 0 || (dist[pairs[u]] > dist[v] && dfs(pairs[u]))) { @@ -33,7 +33,7 @@ bool dfs(int v) { int hopcroft_karp(int l) { // l = #Knoten links int ans = 0; - pairs.assign(sz(adj), -1); + pairs.assign(ssize(adj), -1); dist.resize(l); // Greedy Matching, optionale Beschleunigung. for (int v = 0; v < l; v++) for (int u : adj[v]) diff --git a/content/graph/kruskal.cpp b/content/graph/kruskal.cpp index 987d30b..d42800d 100644 --- a/content/graph/kruskal.cpp +++ b/content/graph/kruskal.cpp @@ -1,4 +1,4 @@ -sort(all(edges)); +ranges::sort(edges, less{}); vector<Edge> mst; ll cost = 0; for (Edge& e : edges) { diff --git a/content/graph/kuhn.cpp b/content/graph/kuhn.cpp index e928387..688c846 100644 --- a/content/graph/kuhn.cpp +++ b/content/graph/kuhn.cpp @@ -12,7 +12,7 @@ bool dfs(int v) { } int kuhn(int l) { // l = #Knoten links. - pairs.assign(sz(adj), -1); + pairs.assign(ssize(adj), -1); int ans = 0; // Greedy Matching. Optionale Beschleunigung. for (int v = 0; v < l; v++) for (int u : adj[v]) diff --git a/content/graph/matching.cpp b/content/graph/matching.cpp index dcaea8c..3619d7c 100644 --- a/content/graph/matching.cpp +++ b/content/graph/matching.cpp @@ -3,19 +3,19 @@ vector<vector<ll>> adj, mat; int max_matching() { int ans = 0; - mat.assign(sz(adj), {}); + mat.assign(ssize(adj), {}); for (int _ = 0; _ < I; _++) { - for (int v = 0; v < sz(adj); v++) { - mat[v].assign(sz(adj), 0); + for (int v = 0; v < ssize(adj); v++) { + mat[v].assign(ssize(adj), 0); for (int u : adj[v]) { if (u < v) { mat[v][u] = rand() % (MOD - 1) + 1; mat[u][v] = MOD - mat[v][u]; }}} - gauss(sz(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ + gauss(ssize(adj), MOD); //LGS @\sourceref{math/lgsFp.cpp}@ int rank = 0; for (auto& row : mat) { - if (*max_element(all(row)) != 0) rank++; + if (*ranges::max_element(row) != 0) rank++; } ans = max(ans, rank / 2); } diff --git a/content/graph/maxWeightBipartiteMatching.cpp b/content/graph/maxWeightBipartiteMatching.cpp index a2b0a80..b6f6ddf 100644 --- a/content/graph/maxWeightBipartiteMatching.cpp +++ b/content/graph/maxWeightBipartiteMatching.cpp @@ -45,6 +45,6 @@ double match(int l, int r) { yx[y] = aug[y]; swap(y, xy[aug[y]]); }} - return accumulate(all(lx), 0.0) + - accumulate(all(ly), 0.0); // Wert des Matchings + return accumulate(begin(lx), end(lx), 0.0) + + accumulate(begin(ly), end(ly), 0.0); // Wert des Matchings } diff --git a/content/graph/minCostMaxFlow.cpp b/content/graph/minCostMaxFlow.cpp index 14a222c..fde95f3 100644 --- a/content/graph/minCostMaxFlow.cpp +++ b/content/graph/minCostMaxFlow.cpp @@ -15,16 +15,16 @@ struct MinCostFlow { adj(n), s(source), t(target) {}; void addEdge(int u, int v, ll c, ll cost) { - adj[u].push_back(sz(edges)); + adj[u].push_back(ssize(edges)); edges.push_back({v, c, cost}); - adj[v].push_back(sz(edges)); + adj[v].push_back(ssize(edges)); edges.push_back({u, 0, -cost}); } bool SPFA() { - pref.assign(sz(adj), -1); - dist.assign(sz(adj), INF); - vector<bool> inqueue(sz(adj)); + pref.assign(ssize(adj), -1); + dist.assign(ssize(adj), INF); + vector<bool> inqueue(ssize(adj)); queue<int> queue; dist[s] = 0; queue.push(s); @@ -59,7 +59,7 @@ struct MinCostFlow { }} void mincostflow() { - con.assign(sz(adj), 0); + con.assign(ssize(adj), 0); maxflow = mincost = 0; while (SPFA()) extend(); } diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp index ec36026..c569df2 100644 --- a/content/graph/pushRelabel.cpp +++ b/content/graph/pushRelabel.cpp @@ -9,8 +9,8 @@ vector<ll> ec; vector<int> cur, H; void addEdge(int u, int v, ll c) { - adj[u].push_back({v, (int)sz(adj[v]), 0, c}); - adj[v].push_back({u, (int)sz(adj[u])-1, 0, 0}); + adj[u].push_back({v, (int)ssize(adj[v]), 0, c}); + adj[v].push_back({u, (int)ssize(adj[u])-1, 0, 0}); } void addFlow(Edge& e, ll f) { @@ -23,7 +23,7 @@ void addFlow(Edge& e, ll f) { } ll maxFlow(int s, int t) { - int n = sz(adj); + int n = ssize(adj); hs.assign(2*n, {}); ec.assign(n, 0); cur.assign(n, 0); @@ -38,9 +38,9 @@ ll maxFlow(int s, int t) { int v = hs[hi].back(); hs[hi].pop_back(); while (ec[v] > 0) { - if (cur[v] == sz(adj[v])) { + if (cur[v] == ssize(adj[v])) { H[v] = 2*n; - for (int i = 0; i < sz(adj[v]); i++) { + for (int i = 0; i < ssize(adj[v]); i++) { Edge& e = adj[v][i]; if (e.c - e.f > 0 && H[v] > H[e.to] + 1) { diff --git a/content/graph/reroot.cpp b/content/graph/reroot.cpp index 379c839..5a9c9d1 100644 --- a/content/graph/reroot.cpp +++ b/content/graph/reroot.cpp @@ -26,11 +26,11 @@ struct Reroot { pref.push_back(takeChild(v, u, w, dp[u])); } auto suf = pref; - partial_sum(all(pref), pref.begin(), comb); + partial_sum(begin(pref), end(pref), begin(pref), comb); exclusive_scan(suf.rbegin(), suf.rend(), suf.rbegin(), E, comb); - for (int i = 0; i < sz(adj[v]); i++) { + for (int i = 0; i < ssize(adj[v]); i++) { auto [u, w] = adj[v][i]; if (u == from) continue; dp[v] = fin(v, comb(pref[i], suf[i + 1])); @@ -40,7 +40,7 @@ struct Reroot { } auto solve() { - dp.assign(sz(adj), E); + dp.assign(ssize(adj), E); dfs0(0); dfs1(0); return dp; diff --git a/content/graph/scc.cpp b/content/graph/scc.cpp index 32f1099..6887712 100644 --- a/content/graph/scc.cpp +++ b/content/graph/scc.cpp @@ -23,11 +23,11 @@ void visit(int v) { }}} void scc() { - inStack.assign(sz(adj), false); - low.assign(sz(adj), -1); - idx.assign(sz(adj), -1); + inStack.assign(ssize(adj), false); + low.assign(ssize(adj), -1); + idx.assign(ssize(adj), -1); counter = sccCounter = 0; - for (int i = 0; i < sz(adj); i++) { + for (int i = 0; i < ssize(adj); i++) { if (low[i] < 0) visit(i); }} diff --git a/content/graph/stoerWagner.cpp b/content/graph/stoerWagner.cpp index 0a6f653..a122488 100644 --- a/content/graph/stoerWagner.cpp +++ b/content/graph/stoerWagner.cpp @@ -7,7 +7,7 @@ vector<vector<Edge>> adj, tmp; vector<bool> erased; void merge(int u, int v) { - tmp[u].insert(tmp[u].end(), all(tmp[v])); + tmp[u].insert(end(tmp[u]), begin(tmp[v]), end(tmp[v])); tmp[v].clear(); erased[v] = true; for (auto& vec : tmp) { @@ -19,13 +19,13 @@ void merge(int u, int v) { ll stoer_wagner() { ll res = INF; tmp = adj; - erased.assign(sz(tmp), false); - for (int i = 1; i < sz(tmp); i++) { + erased.assign(ssize(tmp), false); + for (int i = 1; i < ssize(tmp); i++) { int s = 0; while (erased[s]) s++; priority_queue<pair<ll, int>> pq; pq.push({0, s}); - vector<ll> con(sz(tmp)); + vector<ll> con(ssize(tmp)); ll cur = 0; vector<pair<ll, int>> state; while (!pq.empty()) { diff --git a/content/graph/treeIsomorphism.cpp b/content/graph/treeIsomorphism.cpp index 355fefb..8c2ca21 100644 --- a/content/graph/treeIsomorphism.cpp +++ b/content/graph/treeIsomorphism.cpp @@ -7,9 +7,9 @@ int treeLabel(int v, int from = -1) { if (u == from) continue; children.push_back(treeLabel(u, v)); } - sort(all(children)); + ranges::sort(children); if (known.find(children) == known.end()) { - known[children] = sz(known); + known[children] = ssize(known); } return known[children]; } diff --git a/content/graph/virtualTree.cpp b/content/graph/virtualTree.cpp index 153ed0b..81ba001 100644 --- a/content/graph/virtualTree.cpp +++ b/content/graph/virtualTree.cpp @@ -2,14 +2,14 @@ vector<int> in, out; void virtualTree(vector<int> ind) { // indices of used nodes - sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); - for (int i = 1, n = sz(ind); i < n; i++) { + ranges::sort(ind, {}, [&](int x) { return in[x]; }); + for (int i = 1, n = ssize(ind); i < n; i++) { ind.push_back(lca(ind[i - 1], ind[i])); } - sort(all(ind), [&](int x, int y) { return in[x] < in[y]; }); - ind.erase(unique(all(ind)), ind.end()); + ranges::sort(ind, {}, [&](int x) { return in[x]; }); + ind.erase(begin(ranges::unique(ind)), end(ind)); - int n = sz(ind); + int n = ssize(ind); vector<vector<int>> tree(n); vector<int> st = {0}; for (int i = 1; i < n; i++) { |