Submission #402161

#	Time	Username	Problem	Language	Result	Execution time	Memory
402161		KoD	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	721 ms	57028 KiB

catdog

#include <bits/stdc++.h>
#include "catdog.h"

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T, T Div = 2> constexpr T INFTY = std::numeric_limits<T>::max() / Div;

template <class T> bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

template <class F> struct RecursiveLambda : private F {
    explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class F> constexpr decltype(auto) rec_lambda(F&& f) {
    using G = std::decay_t<F>;
    return RecursiveLambda<G>(std::forward<G>(f));
}

class HeavyLightDecomposition {
    struct Node {
        std::vector<usize> adjacent;
        usize parent, subtree, head, enter, exit;
        Node() = default;
    };
    std::vector<Node> node;

  public:
    HeavyLightDecomposition() = default;
    explicit HeavyLightDecomposition(const std::vector<std::vector<usize>>& tree, const usize root = 0)
        : HeavyLightDecomposition(tree, std::vector<usize>({root})) {}
    explicit HeavyLightDecomposition(const std::vector<std::vector<usize>>& forest, const std::vector<usize>& root)
        : node(forest.size()) {
        for (const auto i : rep(0, size())) node[i].adjacent = forest[i];
        const auto setup = rec_lambda([&](auto&& dfs, const usize u, const usize p) -> void {
            node[u].parent = p;
            node[u].subtree = 1;
            for (const auto v : node[u].adjacent) {
                if (v != p) {
                    dfs(v, u);
                    node[u].subtree += node[v].subtree;
                }
            }
        });
        for (const auto r : root) setup(r, r);
        usize time = 0;
        const auto decompose = rec_lambda([&](auto&& dfs, const usize u, const usize h) -> void {
            node[u].head = h;
            node[u].enter = time;
            time += 1;
            usize select = size();
            for (const auto v : node[u].adjacent) {
                if (v != node[u].parent and (select == size() or node[select].subtree < node[v].subtree)) {
                    select = v;
                }
            }
            if (select != size()) {
                dfs(select, h);
                for (const auto v : node[u].adjacent) {
                    if (v != node[u].parent and v != select) {
                        dfs(v, v);
                    }
                }
            }
            node[u].exit = time;
        });
        for (const auto r : root) decompose(r, r);
    }

    usize size() const { return node.size(); }
    const Node& info(const usize u) const {
        assert(u < size());
        return node[u];
    }

    usize lca(usize u, usize v) const {
        assert(u < size());
        assert(v < size());
        if (node[u].enter > node[v].enter) std::swap(u, v);
        while (node[u].enter < node[v].enter) {
            if (node[u].head == node[v].head) return u;
            v = node[node[v].head].parent;
        }
        return v;
    }

    std::vector<std::pair<usize, usize>> path(usize u, usize p) const {
        assert(u < size());
        assert(p < size());
        assert(node[p].enter <= node[u].enter and node[u].exit <= node[p].exit);
        std::vector<std::pair<usize, usize>> ret;
        while (node[u].head != node[p].head) {
            ret.emplace_back(u, node[u].head);
            u = node[node[u].head].parent;
        }
        ret.emplace_back(u, p);
        return ret;
    }
};

class revrep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { --itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr revrep(const usize first, const usize last) noexcept
        : first(last - 1), last(std::min(first, last) - 1) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr u64 ceil_log2(const u64 x) {
    u64 e = 0;
    while (((u64)1 << e) < x) ++e;
    return e;
}

template <class Monoid> class SegmentTree {
    using M = Monoid;
    usize internal_size, seg_size;
    std::vector<M> data;

    void fetch(const usize k) { data[k] = data[2 * k] + data[2 * k + 1]; }

  public:
    explicit SegmentTree(const usize size = 0, const M& value = M::zero()) : SegmentTree(std::vector<M>(size, value)) {}
    explicit SegmentTree(const std::vector<M>& vec) : internal_size(vec.size()) {
        seg_size = 1 << ceil_log2(internal_size);
        data = std::vector<M>(2 * seg_size, M::zero());
        for (const usize i : rep(0, internal_size)) data[seg_size + i] = vec[i];
        for (const usize i : revrep(1, seg_size)) fetch(i);
    }

    usize size() const { return internal_size; }

    void assign(usize i, const M& value) {
        assert(i < internal_size);
        i += seg_size;
        data[i] = value;
        while (i > 1) {
            i >>= 1;
            fetch(i);
        }
    }

    M fold() const { return data[1]; }
    M fold(usize l, usize r) const {
        assert(l <= r and r <= internal_size);
        l += seg_size;
        r += seg_size;
        M ret_l = M::zero(), ret_r = M::zero();
        while (l < r) {
            if (l & 1) ret_l = ret_l + data[l++];
            if (r & 1) ret_r = data[--r] + ret_r;
            l >>= 1;
            r >>= 1;
        }
        return ret_l + ret_r;
    }

    template <class F> usize max_right(usize l, const F& f) const {
        assert(l <= internal_size);
        assert(f(M::zero()));
        if (l == internal_size) return internal_size;
        l += seg_size;
        M sum = M::zero();
        do {
            while (!(l & 1)) l >>= 1;
            if (!f(sum + data[l])) {
                while (l < seg_size) {
                    l = 2 * l;
                    if (f(sum + data[l])) sum = sum + data[l++];
                }
                return l - seg_size;
            }
            sum = sum + data[l++];
        } while ((l & -l) != l);
        return internal_size;
    }

    template <class F> usize min_left(usize r, const F& f) const {
        assert(r <= internal_size);
        assert(f(M::zero()));
        if (r == 0) return 0;
        r += seg_size;
        M sum = M::zero();
        do {
            r -= 1;
            while (r > 1 and (r & 1)) r >>= 1;
            if (!f(data[r] + sum)) {
                while (r < seg_size) {
                    r = 2 * r + 1;
                    if (f(data[r] + sum)) sum = data[r--] + sum;
                }
                return r + 1 - seg_size;
            }
            sum = data[r] + sum;
        } while ((r & -r) != r);
        return 0;
    }
};

template <class T> using Vec = std::vector<T>;

namespace catdog {

constexpr usize MAX = INFTY<usize, 3>;

struct Monoid {
    std::array<std::array<usize, 2>, 2> cost;
    static constexpr Monoid zero() { return Monoid{{0, MAX, MAX, 0}}; }
    Monoid operator+(const Monoid& other) const {
        std::array<std::array<usize, 2>, 2> ret{};
        ret[0][0] = ret[0][1] = ret[1][0] = ret[1][1] = MAX;
        for (const auto i : rep(0, 2))
            for (const auto j : rep(0, 2))
                for (const auto k : rep(0, 2))
                    for (const auto l : rep(0, 2)) setmin(ret[i][l], cost[i][j] + other.cost[k][l] + (j ^ k));
        return Monoid{ret};
    }
};

usize N;
HeavyLightDecomposition hld;
Vec<usize> bad, len;
Vec<std::array<usize, 2>> sum;
SegmentTree<Monoid> seg;

void init(const Vec<Vec<usize>>& graph) {
    N = graph.size();
    hld = HeavyLightDecomposition(graph);
    bad = Vec<usize>(N, 2);
    len = Vec<usize>(N, 0);
    for (const auto u : rep(0, N)) {
        len[hld.info(u).head] += 1;
    }
    sum = Vec<std::array<usize, 2>>(N);
    seg = SegmentTree<Monoid>(N);
}

std::array<usize, 2> get(const Monoid& m) {
    return {std::min(m.cost[0][0], m.cost[0][1]), std::min(m.cost[1][0], m.cost[1][1])};
}

usize set(usize u, const usize k) {
    u -= 1;
    bad[u] = k;
    while (true) {
        const auto h = hld.info(u).head;
        const auto cur = get(seg.fold(hld.info(h).enter, hld.info(h).enter + len[h]));
        {
            std::array<std::array<usize, 2>, 2> arr;
            for (const auto i : rep(0, 2)) {
                arr[i].fill(MAX);
                if (i != bad[u]) {
                    arr[i][i] = sum[u][i];
                }
            }
            seg.assign(hld.info(u).enter, Monoid{arr});
        }
        const auto next = get(seg.fold(hld.info(h).enter, hld.info(h).enter + len[h]));
        const auto p = hld.info(h).parent;
        if (p == h) {
            return std::min(next[0], next[1]);
        }
        for (const auto i : rep(0, 2)) {
            sum[p][i] -= cur[i];
            sum[p][i] += next[i];
        }
        u = p;
    }
    assert(false);
    return 0;
}

};  // namespace catdog

void initialize(int N, Vec<int> A, Vec<int> B) {
    Vec<Vec<usize>> graph(N);
    for (const auto i : rep(0, N - 1)) {
        A[i] -= 1;
        B[i] -= 1;
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }
    catdog::init(graph);
}

int cat(int v) { return catdog::set(v, 0); }

int dog(int v) { return catdog::set(v, 1); }

int neighbor(int v) { return catdog::set(v, 2); }

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62