oj.uz

Submission #402161

# Submission time Handle Problem Language Result Execution time Memory
402161 2021-05-11T11:37:48 Z KoD Cats or Dogs (JOI18_catdog) C++17
100 / 100
 721 ms 57028 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 2 ms 560 KB Output is correct
20 Correct 1 ms 292 KB Output is correct
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 296 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 3 ms 560 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 2 ms 332 KB Output is correct

Subtask #3
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 3 ms 460 KB Output is correct
18 Correct 3 ms 588 KB Output is correct
19 Correct 2 ms 560 KB Output is correct
20 Correct 1 ms 292 KB Output is correct
21 Correct 3 ms 332 KB Output is correct
22 Correct 2 ms 296 KB Output is correct
23 Correct 3 ms 460 KB Output is correct
24 Correct 3 ms 560 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 2 ms 588 KB Output is correct
29 Correct 2 ms 716 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 417 ms 17884 KB Output is correct
34 Correct 131 ms 20508 KB Output is correct
35 Correct 364 ms 13740 KB Output is correct
36 Correct 634 ms 31948 KB Output is correct
37 Correct 24 ms 9804 KB Output is correct
38 Correct 721 ms 34548 KB Output is correct
39 Correct 668 ms 34628 KB Output is correct
40 Correct 694 ms 34628 KB Output is correct
41 Correct 688 ms 34600 KB Output is correct
42 Correct 640 ms 34628 KB Output is correct
43 Correct 665 ms 34584 KB Output is correct
44 Correct 643 ms 34584 KB Output is correct
45 Correct 666 ms 34600 KB Output is correct
46 Correct 641 ms 34604 KB Output is correct
47 Correct 703 ms 34628 KB Output is correct
48 Correct 170 ms 27576 KB Output is correct
49 Correct 191 ms 32808 KB Output is correct
50 Correct 62 ms 7240 KB Output is correct
51 Correct 79 ms 13736 KB Output is correct
52 Correct 30 ms 7112 KB Output is correct
53 Correct 260 ms 33444 KB Output is correct
54 Correct 199 ms 15204 KB Output is correct
55 Correct 561 ms 26284 KB Output is correct
56 Correct 296 ms 16196 KB Output is correct
57 Correct 394 ms 31828 KB Output is correct
58 Correct 37 ms 15064 KB Output is correct
59 Correct 63 ms 10788 KB Output is correct
60 Correct 169 ms 30136 KB Output is correct
61 Correct 169 ms 31004 KB Output is correct
62 Correct 108 ms 26672 KB Output is correct
63 Correct 74 ms 25116 KB Output is correct
64 Correct 101 ms 30148 KB Output is correct
65 Correct 127 ms 48800 KB Output is correct
66 Correct 94 ms 10764 KB Output is correct
67 Correct 108 ms 36676 KB Output is correct
68 Correct 221 ms 48296 KB Output is correct
69 Correct 44 ms 3772 KB Output is correct
70 Correct 9 ms 716 KB Output is correct
71 Correct 80 ms 23048 KB Output is correct
72 Correct 129 ms 43144 KB Output is correct
73 Correct 331 ms 57028 KB Output is correct
74 Correct 355 ms 46380 KB Output is correct
75 Correct 243 ms 56772 KB Output is correct
76 Correct 237 ms 53028 KB Output is correct
77 Correct 339 ms 47396 KB Output is correct