232-aka-pretty-pi 님의 블로그 232-aka-pretty-pi 님의 블로그

namespace line_detail { struct Line { long long k; long long m; mutable long long p; bool operator > { constexpr static long long inf = std::numeric_limits::max(); static long long div(long long x, long long y) { return x / y - ((x ^ y) p = inf; return false; } if (x->k == y->k) { x->p = (x->m > y->m ? inf : -inf); } else { x->p = div(y->m - x->m, x->k -..

https://www.acmicpc.net/problem/23844몇 개월 전에 랜디하다가 못 푼 문제인데, 풀이를 알게 되어 적어본다.트리의 노드들을 깊이에 따라 분류 했을 때, 각 깊이에서 살아 남는 노드는 k개 이하일 것이다.놀랍게도, 어떤 깊이 d에 속하는 노드가 c1개면, 이중 min(c1, k)개를 살릴 수 있다.트리를 깊이가 깊은 노드부터 구성하자.깊이 d + 1에 속하는 노드가 c2개였다면, 깊이 d + 1에서는 min(c2, k)개의 노드를 살렸을 것이다.이 노드들을 계속 살려야 하므로, 이 노드들의 부모 정점도 살려야 하는데, 어차피 이 노드들의 부모 정점의 수가 (중복을 제거하면) min(c1, k)개를 넘지 않는다.따라서 이러한 트리를 구성할 수 있다.#include int main..

use Dinic instead.template struct MaximumFlow { struct Edge { int to; T cap; }; int n; std::vector edges; std::vector> g; MaximumFlow(int _n) : n(_n) { g.resize(n); } void addEdge(int u, int v, T cap) { assert(0 = 0); g[u].push_back(int(edges.size())); edges.push_back({v, cap}); g[v].push_back(int(edges.size())); edges.push_back({u, 0}); } T augment(int s, int t..

linear inclusive?can't just do ccw  upd : now all in Geometry..Polygon getConvexHull(Polygon poly) { std::sort(poly.begin(), poly.end()); poly.resize(std::unique(poly.begin(), poly.end()) - poly.begin()); if (int(poly.size()) start + 1 && ccw(hull[hull.size() - 2], hull.back(), pt)

using F = long double;template struct PointBase { constexpr static T eps = T(1E-9); T x; T y; PointBase() : x(0), y(0) { void(0); } PointBase(T x, T y) : x(x), y(y) { void(0); } friend PointBase operator-(const PointBase& a, const PointBase& b) { return {a.x - b.x, a.y - b.y}; } friend PointBase operator+(const PointBase& a, const PointBase& b) { return {a.x + b.x, a.y + b...

struct SuffixArray { int n; std::vector sa; std::vector rank; std::vector lcp; template SuffixArray(const C& s) { assert(!s.empty() && "at Suffix Array constructor"); n = int(s.size()); sa.resize(n); rank.resize(n); lcp.resize(n); std::iota(sa.begin(), sa.end(), 0); std::sort(sa.begin(), sa.end(), [&](int i, int j) { return s[i] sorted_by_second(k); std::io..

template struct Graph { struct Edge { int from; int to; T cost; }; int n; std::vector> g; std::vector edges; Graph(int _n) : n(_n) { g.resize(n); } virtual int addEdge(int from, int to, T cost) = 0;};template struct DiGraph : Graph { using Graph::n; using Graph::g; using Graph::edges; DiGraph(int _n) : Graph(_n) { void(0); } [[maybe_unused]] int addEdge(int from, int..

template struct SlidingQueue { F func; std::vector tail; std::vector fhead; std::vector ftail; SlidingQueue(const F& _func = F {}) : func(_func) { void(0); } [[nodiscard]] int size() const { return int(fhead.size() + ftail.size()); } [[nodiscard]] bool empty() const { return size() == 0; } [[nodiscard]] T get() const { if (!fhead.empty() && !ftail.empty()) { return fu..