rcpl

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ruthen71/rcpl

:heavy_check_mark: verify/graph/euler_tour.test.cpp

Depends on

Code

#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D"

#include <iostream>

#include "algebra/monoid/monoid_plus.hpp"
#include "segment_tree/segment_tree.hpp"
#include "graph/euler_tour.hpp"
#include "graph/read_graph.hpp"

int main() {
    int N;
    std::cin >> N;
    Graph<int> g(N);

    std::vector<int> id(N, -1);
    for (int i = 0; i < N; i++) {
        int K;
        std::cin >> K;
        for (int j = 0; j < K; j++) {
            int c;
            std::cin >> c;
            id[c] = g.add_edge(i, c, 0);
        }
    }

    EulerTour et(g);
    SegmentTree<MonoidPlus<long long>> seg(2 * N - 2);
    int Q;
    std::cin >> Q;
    for (int q = 0; q < Q; q++) {
        int type;
        std::cin >> type;
        if (type == 0) {
            int v, w;
            std::cin >> v >> w;
            int eid = id[v];
            seg.add(et.esl[eid], w);
            seg.add(et.esr[eid], -w);
        } else {
            int u;
            std::cin >> u;
            std::cout << seg.prod(0, et.vsl[u]) << '\n';
        }
    }
    return 0;
}
#line 1 "verify/graph/euler_tour.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_D"

#include <iostream>

#line 2 "algebra/monoid/monoid_plus.hpp"

template <class T> struct MonoidPlus {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return a + b;
    }
    static constexpr T identity() noexcept { return T(0); }
    static constexpr T inverse(const T& a) noexcept { return -a; }
    static constexpr bool commutative = true;
};
#line 2 "segment_tree/segment_tree.hpp"

#line 2 "misc/bit_ceil.hpp"

#include <cassert>

#if __cplusplus >= 202002L
#include <bit>
#endif

// bit_ceil
// (0, 1, 2, 3, 4) -> (1, 1, 2, 4, 4)
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int x) {
    unsigned int p = 1;
    while (p < x) p *= 2;
    return p;
}
unsigned long long int bit_ceil(unsigned long long int x) {
    unsigned long long int p = 1;
    while (p < x) p *= 2;
    return p;
}
#endif
int bit_ceil(int x) {
    assert(x >= 0);
    return bit_ceil((unsigned int)(x));
}
long long int bit_ceil(long long int x) {
    assert(x >= 0);
    return bit_ceil((unsigned long long int)(x));
}
#line 2 "misc/countr_zero.hpp"

#if __cplusplus >= 202002L
#include <bit>
#endif

// countr_zero
// (000, 001, 010, 011, 100) -> (32, 0, 1, 0, 2)
#if __cplusplus >= 202002L
using std::countr_zero;
#else
int countr_zero(unsigned int x) {
    return x == 0 ? 32 : __builtin_ctz(x);
}
int countr_zero(unsigned long long int x) {
    return x == 0 ? 64 : __builtin_ctzll(x);
}
#endif
int countr_zero(int x) { return countr_zero((unsigned int)(x)); }
int countr_zero(long long int x) {
    return countr_zero((unsigned long long int)(x));
}
#line 5 "segment_tree/segment_tree.hpp"

#line 7 "segment_tree/segment_tree.hpp"
#include <vector>

// Segment Tree
template <class MS> struct SegmentTree {
  public:
    using S = typename MS::value_type;

    SegmentTree() = default;

    explicit SegmentTree(int n)
        : SegmentTree(std::vector<S>(n, MS::identity())) {}

    explicit SegmentTree(const std::vector<S>& v) : n((int)(v.size())) {
        size = bit_ceil(n);
        log = countr_zero(size);
        d = std::vector<S>(size << 1, MS::identity());
        for (int i = 0; i < n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, const S& x) {
        assert(0 <= p and p < n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    void add(int p, const S& x) {
        assert(0 <= p and p < n);
        p += size;
        d[p] = MS::operation(d[p], x);
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return d[p + size];
    }

    S get(int p) const {
        assert(0 <= p && p < n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l and l <= r and r <= n);
        S sml = MS::identity(), smr = MS::identity();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = MS::operation(sml, d[l++]);
            if (r & 1) smr = MS::operation(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return MS::operation(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <class G> int max_right(int l, G& g) const {
        assert(0 <= l and l <= n);
        assert(g(MS::identity()));
        if (l == n) return n;
        l += size;
        S sm = MS::identity();
        do {
            while ((l & 1) == 0) l >>= 1;
            if (!g(MS::operation(sm, d[l]))) {
                while (l < size) {
                    l <<= 1;
                    if (g(MS::operation(sm, d[l]))) {
                        sm = MS::operation(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = MS::operation(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return n;
    }

    template <class G> int min_left(int r, G& g) const {
        assert(0 <= r and r <= n);
        assert(g(MS::identity()));
        if (r == 0) return 0;
        r += size;
        S sm = MS::identity();
        do {
            r--;
            while (r > 1 and (r & 1)) r >>= 1;
            if (!g(MS::operation(d[r], sm))) {
                while (r < size) {
                    r = (r << 1) | 1;
                    if (g(MS::operation(d[r], sm))) {
                        sm = MS::operation(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = MS::operation(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

    std::vector<S> make_vector() const {
        std::vector<S> vec(n);
        for (int i = 0; i < n; i++) vec[i] = get(i);
        return vec;
    }

  private:
    int n, log, size;
    std::vector<S> d;

    inline void update(int k) {
        d[k] = MS::operation(d[k << 1], d[(k << 1) | 1]);
    }
};
#line 2 "graph/euler_tour.hpp"

#line 2 "graph/graph_template.hpp"

#line 5 "graph/graph_template.hpp"

template <class T> struct Edge {
    int from, to;
    T cost;
    int id;

    Edge() = default;
    Edge(const int from, const int to, const T cost = T(1), const int id = -1)
        : from(from), to(to), cost(cost), id(id) {}

    friend bool operator<(const Edge<T>& a, const Edge<T>& b) {
        return a.cost < b.cost;
    }

    friend std::ostream& operator<<(std::ostream& os, const Edge<T>& e) {
        // output format: {id: cost(from, to) = cost}
        return os << "{" << e.id << ": cost(" << e.from << ", " << e.to
                  << ") = " << e.cost << "}";
    }
};
template <class T> using Edges = std::vector<Edge<T>>;

template <class T> struct Graph {
    struct EdgeIterators {
      public:
        using Iterator = typename std::vector<Edge<T>>::iterator;
        EdgeIterators() = default;
        EdgeIterators(const Iterator& begit, const Iterator& endit)
            : begit(begit), endit(endit) {}
        Iterator begin() const { return begit; }
        Iterator end() const { return endit; }
        size_t size() const { return std::distance(begit, endit); }
        Edge<T>& operator[](int i) const { return begit[i]; }

      private:
        Iterator begit, endit;
    };

    int n, m;
    bool is_build, is_directed;
    std::vector<Edge<T>> edges;

    // CSR (Compressed Row Storage) 形式用
    std::vector<int> start;
    std::vector<Edge<T>> csr_edges;

    Graph() = default;
    Graph(const int n, const bool directed = false)
        : n(n), m(0), is_build(false), is_directed(directed), start(n + 1, 0) {}

    // 辺を追加し, その辺が何番目に追加されたかを返す
    int add_edge(const int from,
                 const int to,
                 const T cost = T(1),
                 int id = -1) {
        assert(!is_build);
        assert(0 <= from and from < n);
        assert(0 <= to and to < n);
        if (id == -1) id = m;
        edges.emplace_back(from, to, cost, id);
        return m++;
    }

    // CSR 形式でグラフを構築
    void build() {
        assert(!is_build);
        for (auto&& e : edges) {
            start[e.from + 1]++;
            if (!is_directed) start[e.to + 1]++;
        }
        for (int v = 0; v < n; v++) start[v + 1] += start[v];
        auto counter = start;
        csr_edges.resize(start.back() + 1);
        for (auto&& e : edges) {
            csr_edges[counter[e.from]++] = e;
            if (!is_directed)
                csr_edges[counter[e.to]++] = Edge(e.to, e.from, e.cost, e.id);
        }
        is_build = true;
    }

    EdgeIterators operator[](int i) {
        if (!is_build) build();
        return EdgeIterators(csr_edges.begin() + start[i],
                             csr_edges.begin() + start[i + 1]);
    }

    size_t size() const { return (size_t)(n); }

    friend std::ostream& operator<<(std::ostream& os, Graph<T>& g) {
        os << "[";
        for (int i = 0; i < (int)(g.size()); i++) {
            os << "[";
            for (int j = 0; j < (int)(g[i].size()); j++) {
                os << g[i][j];
                if (j + 1 != (int)(g[i].size())) os << ", ";
            }
            os << "]";
            if (i + 1 != (int)(g.size())) os << ", ";
        }
        return os << "]";
    }
};
#line 4 "graph/euler_tour.hpp"

#include <tuple>

// Euler Tour
// O(n + m)
// 辺と頂点のうち, 変化させるものを要素と見て, そうでないもので要素を区切ると考えると良い
template <class T> struct EulerTour {
    int n;
    std::vector<int> vertices;  // DFS で訪問する頂点の番号を並べたもの, 2 * n - 1 要素
    std::vector<int> edges;     // DFS で通る辺の番号を並べたもの, 2 * n - 2 要素
    std::vector<int> dir;       // DFS で通る辺の向きが 0 = 子供方向, 1 = 親方向
    std::vector<int> vsl;       // vsl[v]: vertices[i] = v となる i の最小値
    std::vector<int> vsr;       // vsr[v]: vertices[i] = v となる i の最大値
    std::vector<int> esl;       // esl[e]: edges[i] = e かつ dir[i] = 0 となる i
    std::vector<int> esr;       // esr[e]: edges[i] = e かつ dir[i] = 1 となる i

    EulerTour(Graph<T>& g, const int root = 0) : n((int)(g.size())), vsl(n, 2 * n - 1), vsr(n, -1), esl(n - 1, -1), esr(n - 1, -1) {
        vertices.reserve(2 * n - 1);
        edges.reserve(2 * n - 2);
        dir.reserve(2 * n - 2);

        auto dfs = [&](auto f, int cur, int par) -> void {
            for (auto&& e : g[cur]) {
                if (e.to == par) continue;
                // 頂点を追加
                vertices.emplace_back(cur);
                // 子供方向の辺を追加
                edges.emplace_back(e.id);
                dir.emplace_back(0);
                // DFS
                f(f, e.to, cur);
                // 親方向の辺を追加
                edges.emplace_back(e.id);
                dir.emplace_back(1);
            }
            // 頂点を追加
            vertices.emplace_back(cur);
        };
        dfs(dfs, root, -1);
        for (int i = 2 * n - 2; i >= 0; i--) vsl[vertices[i]] = i;
        for (int i = 0; i < 2 * n - 1; i++) vsr[vertices[i]] = i;
        for (int i = 0; i < 2 * n - 2; i++) (dir[i] == 0 ? esl[edges[i]] : esr[edges[i]]) = i;
    }
};
#line 2 "graph/read_graph.hpp"

#line 4 "graph/read_graph.hpp"

template <class T>
Graph<T> read_graph(const int n,
                    const int m,
                    const bool weight = false,
                    const bool directed = false,
                    const int offset = 1) {
    Graph<T> g(n, directed);
    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        a -= offset, b -= offset;
        T c = 1;
        if (weight) std::cin >> c;
        g.add_edge(a, b, c);
    }
    g.build();
    return g;
}

template <class T>
Graph<T> read_parent(const int n,
                     const bool weight = false,
                     const bool directed = false,
                     const int offset = 1) {
    Graph<T> g(n, directed);
    for (int i = 1; i < n; i++) {
        int p;
        std::cin >> p;
        p -= offset;
        T c = 1;
        if (weight) std::cin >> c;
        g.add_edge(p, i, c);
    }
    g.build();
    return g;
}
#line 10 "verify/graph/euler_tour.test.cpp"

int main() {
    int N;
    std::cin >> N;
    Graph<int> g(N);

    std::vector<int> id(N, -1);
    for (int i = 0; i < N; i++) {
        int K;
        std::cin >> K;
        for (int j = 0; j < K; j++) {
            int c;
            std::cin >> c;
            id[c] = g.add_edge(i, c, 0);
        }
    }

    EulerTour et(g);
    SegmentTree<MonoidPlus<long long>> seg(2 * N - 2);
    int Q;
    std::cin >> Q;
    for (int q = 0; q < Q; q++) {
        int type;
        std::cin >> type;
        if (type == 0) {
            int v, w;
            std::cin >> v >> w;
            int eid = id[v];
            seg.add(et.esl[eid], w);
            seg.add(et.esr[eid], -w);
        } else {
            int u;
            std::cin >> u;
            std::cout << seg.prod(0, et.vsl[u]) << '\n';
        }
    }
    return 0;
}
Back to top page