Submission #519447

#	Time	Username	Problem	Language	Result	Execution time	Memory
519447		Cyanmond	Bridges (APIO19_bridges)	C++17	100 / 100	2958 ms	14460 KiB

bridges

#line 1 "paper.cpp"
#include <bits/stdc++.h>

#line 3 "library2/utility/len.hpp"

template <class Container> int len(const Container&c){
    return static_cast<int>(std::size(c));
}
#line 7 "library2/graph/rollback_union_find.hpp"

class RollbackUnionFind {
    std::vector<int> data;
    std::stack<std::pair<int, int>> history;

  public:
    explicit RollbackUnionFind(const int n_) : data(n_, -1) {}

    int size() const noexcept {
        return len(data);
    }

    int get_state() const {
        return len(history) / 2;
    }

    int leader(int v) const {
        assert(0 <= v and v < size());
        while (data[v] >= 0) {
            v = data[v];
        }
        return v;
    }

    int size(const int v) const {
        assert(0 <= v and v < size());
        return -data[leader(v)];
    }

    bool is_same(const int x, const int y) const {
        return leader(x) == leader(y);
    }

    bool unite(int x, int y) {
        assert(0 <= x and x < size());
        assert(0 <= y and y < size());
        x = leader(x);
        y = leader(y);
        if (x == y) {
            return false;
        }
        if (data[x] > data[y]) {
            std::swap(x, y);
        }
        history.emplace(x, data[x]);
        history.emplace(y, data[y]);
        data[x] += data[y];
        data[y] = x;
        return true;
    }

    int root_press(int v) {
        if (data[v] >= 0) {
            return data[v] = root_press(data[v]);
        } else {
            return v;
        }
    }

    void undo() {
        assert(not history.empty());
        data[history.top().first] = history.top().second;
        history.pop();
        data[history.top().first] = history.top().second;
        history.pop();
    }

    void rollback(int steps) {
        assert(0 <= steps and 2 * steps <= len(history));
        while (steps != 0) {
            --steps;
            undo();
        }
    }
};
#line 3 "library2/utility/int_alias.hpp"

using i8 = std::int8_t;
using u8 = std::uint8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
#line 3 "library2/utility/rep.hpp"

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

  public:
    explicit constexpr Range(const int f, const int l) noexcept
        : first(f), last(std::max(f, l)) {}
    constexpr Iterator begin() const noexcept {
        return first;
    }
    constexpr Iterator end() const noexcept {
        return last;
    }
};

constexpr Range rep(const int l, const int r) noexcept {
    return Range(l, r);
}
constexpr Range rep(const int n) noexcept {
    return Range(0, n);
}
#line 3 "library2/utility/scan.hpp"

template <typename T = int> T scan() {
    T ret;
    std::cin >> ret;
    return ret;
}
#line 5 "library2/utility/upb.hpp"

template <class Container, class T> constexpr int upb(const Container &c, const T &val) {
    return static_cast<int>(std::distance(c.cbegin(), std::upper_bound(c.cbegin(), c.cend(), val)));
}
#line 9 "paper.cpp"

int main() {
    const int N = scan();
    const int M = scan();
    std::vector<int> U(M), V(M), D(M);
    for (const int i : rep(M)) {
        U[i] = scan() - 1;
        V[i] = scan() - 1;
        D[i] = scan();
    }
    const int Q = scan();
    std::vector<int> T(Q), A(Q), B(Q);
    for (const int i : rep(Q)) {
        T[i] = scan();
        A[i] = scan() - 1;
        B[i] = scan();
    }

    std::vector<int> answer(Q);

    auto solve_sub = [&](const int l, const int r, std::vector<int> &F) {
        assert(len(F) == M);
        assert(0 <= l and l <= r and r <= Q);

        std::vector<bool> is_changed(M);
        std::vector<std::vector<std::pair<int, int>>> history(M);
        for (const int i : rep(M)) {
            history[i].push_back({-1, F[i]});
        }

        for (const int i : rep(l, r)) {
            if (T[i] == 1) {
                is_changed[A[i]] = true;
                history[A[i]].push_back({i, B[i]});
                F[A[i]] = B[i];
            }
        }

        RollbackUnionFind uft(N);

        std::vector<int> edges;
        for (const int i : rep(M)) {
            if (not is_changed[i]) {
                edges.push_back(i);
            }
        }
        std::sort(edges.begin(), edges.end(),
                  [&](const int a, const int b) { return F[a] > F[b]; });

        std::vector<int> queries;
        for (const int i : rep(l, r)) {
            if (T[i] == 2) {
                queries.push_back(i);
            }
        }
        std::sort(queries.begin(), queries.end(),
                  [&](const int a, const int b) { return B[a] > B[b]; });

        int idx = 0;

        for (const int x : queries) {
            while (idx != len(edges) and F[edges[idx]] >= B[x]) {
                uft.unite(U[edges[idx]], V[edges[idx]]);
                uft.root_press(U[edges[idx]]);
                uft.root_press(V[edges[idx]]);
                ++idx;
            }

            int count_back = 0;
            for (const int i : rep(l, r)) {
                if (T[i] == 1) {
                    const int p = upb(history[A[i]], std::make_pair(x, 0));
                    if (history[A[i]][p - 1].second >= B[x]) {
                        if (uft.unite(U[A[i]], V[A[i]])) {
                            ++count_back;
                        }
                    }
                }
            }

            answer[x] = uft.size(A[x]);
            uft.rollback(count_back);
        }
    };

    constexpr int block_size = 1000;

    for (int i = 0; i < Q; i += block_size) {
        solve_sub(i, std::min(i + block_size, Q), D);
    }

    for (const auto e : answer) {
        if (e != 0) {
            std::cout << e << std::endl;
        }
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27