#955959 (C++23) No.1170 Never Want to Walk

提出ソース

結果

問題	No.1170 Never Want to Walk
ユーザー	nono00
提出日時	2024-02-26 08:29:58
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	550 ms / 2,000 ms
コード長	8,571 bytes
コンパイル時間	2,038 ms
コンパイル使用メモリ	138,540 KB
実行使用メモリ	215,584 KB
最終ジャッジ日時	2024-09-29 11:35:23
合計ジャッジ時間	10,217 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	2 ms 6,816 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,820 KB
testcase_10	AC	2 ms 6,820 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	3 ms 6,816 KB
testcase_13	AC	3 ms 6,816 KB
testcase_14	AC	3 ms 6,816 KB
testcase_15	AC	3 ms 6,820 KB
testcase_16	AC	3 ms 6,816 KB
testcase_17	AC	3 ms 6,816 KB
testcase_18	AC	3 ms 6,824 KB
testcase_19	AC	3 ms 6,820 KB
testcase_20	AC	3 ms 6,816 KB
testcase_21	AC	3 ms 6,820 KB
testcase_22	AC	4 ms 6,820 KB
testcase_23	AC	4 ms 6,816 KB
testcase_24	AC	3 ms 6,816 KB
testcase_25	AC	3 ms 6,816 KB
testcase_26	AC	4 ms 6,816 KB
testcase_27	AC	232 ms 74,660 KB
testcase_28	AC	231 ms 74,200 KB
testcase_29	AC	232 ms 75,708 KB
testcase_30	AC	233 ms 74,476 KB
testcase_31	AC	232 ms 73,636 KB
testcase_32	AC	441 ms 183,828 KB
testcase_33	AC	550 ms 191,132 KB
testcase_34	AC	447 ms 185,900 KB
testcase_35	AC	481 ms 215,584 KB
testcase_36	AC	463 ms 183,352 KB
testcase_37	AC	507 ms 179,632 KB
testcase_38	AC	466 ms 181,332 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <vector>

#include <utility>
#include <vector>

#include <iterator>
#include <ranges>
#include <vector>

namespace nono {

template <class T>
struct EdgeBase {
    int from;
    int to;
    T weight;
    EdgeBase() {}
    EdgeBase(int from, int to, T weight = 1): from(from), to(to), weight(weight) {}
};

using Edge = EdgeBase<int>;
template <class T>
using WeightedEdge = EdgeBase<T>;

template <class T>
class Graph {
    struct Edge_ {
        int to;
        T weight;
        int id;
    };

    using iterator = std::vector<Edge_>::iterator;
    using const_iterator = std::vector<Edge_>::const_iterator;
    using subrange = std::ranges::subrange<iterator, iterator>;
    using const_subrange = std::ranges::subrange<const_iterator, const_iterator>;

  public:
    template <class U>
    friend Graph<U> to_undirected_graph(int n, const std::vector<EdgeBase<U>>& edges);
    template <class U>
    friend Graph<U> to_directed_graph(int n, const std::vector<EdgeBase<U>>& edges);

    subrange operator[](int i) {
        return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]);
    }
    const_subrange operator[](int i) const {
        return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]);
    }

    int size() const {
        return n_;
    }
    bool is_directed() const {
        return directed_;
    }
    bool is_undirected() const {
        return !is_directed();
    }

  private:
    Graph(int n, const std::vector<EdgeBase<T>>& edges, bool directed)
        : n_(n),
          indptr_(n + 1),
          edges_(directed ? edges.size() : 2 * edges.size()),
          directed_(directed) {
        for (const auto& edge: edges) {
            indptr_[edge.from + 1]++;
            if (!directed) indptr_[edge.to + 1]++;
        }
        for (int i = 0; i < n_; i++) {
            indptr_[i + 1] += indptr_[i];
        }
        auto index = indptr_;
        for (int i = 0; i < std::ssize(edges); i++) {
            const auto& edge = edges[i];
            edges_[index[edge.from]++] = Edge_(edge.to, edge.weight, i);
            if (!directed) edges_[index[edge.to]++] = Edge_(edge.from, edge.weight, i);
        }
    }

    int n_;
    std::vector<int> indptr_;
    std::vector<Edge_> edges_;
    bool directed_;
};

template <class T>
Graph<T> to_undirected_graph(int n, const std::vector<EdgeBase<T>>& edges) {
    return Graph<T>(n, edges, false);
}

template <class T>
Graph<T> to_directed_graph(int n, const std::vector<EdgeBase<T>>& edges) {
    return Graph<T>(n, edges, true);
}

}  //  namespace nono

namespace nono {

template <class T>
struct SegmentEdge {
    std::pair<int, int> from;
    std::pair<int, int> to;
    T weight;
};

template <class T>
std::pair<Graph<T>, std::vector<int>> to_graph(int n, const std::vector<SegmentEdge<T>>& seg_edges) {
    int m = seg_edges.size();
    std::vector<WeightedEdge<T>> edges;

    auto from = [n](int id) {
        return (n <= id ? id : id + 2 * n);
    };
    auto to = [](int id) {
        return id;
    };

    for (int u = n - 1; u > 0; u--) {
        edges.emplace_back(to(u), to(2 * u), 0);
        edges.emplace_back(to(u), to(2 * u + 1), 0);
    }

    for (int u = n - 1; u > 0; u--) {
        edges.emplace_back(from(2 * u), from(u), 0);
        edges.emplace_back(from(2 * u + 1), from(u), 0);
    }

    for (int i = 0; i < m; i++) {
        int edge_id = i + 3 * n;
        {
            auto [left, right] = seg_edges[i].from;
            for (left += n, right += n; left < right; left >>= 1, right >>= 1) {
                if (left & 1) {
                    edges.emplace_back(from(left++), edge_id, 0);
                }
                if (right & 1) {
                    edges.emplace_back(from(--right), edge_id, 0);
                }
            }
        }
        {
            auto [left, right] = seg_edges[i].to;
            for (left += n, right += n; left < right; left >>= 1, right >>= 1) {
                if (left & 1) {
                    edges.emplace_back(edge_id, to(left++), seg_edges[i].weight);
                }
                if (right & 1) {
                    edges.emplace_back(edge_id, to(--right), seg_edges[i].weight);
                }
            }
        }
    }
    std::vector<int> mapping(3 * n + m, -1);
    for (int i = 0; i < n; i++) {
        mapping[i + n] = i;
    }
    return {to_directed_graph(3 * n + m, edges), mapping};
}

}  //  namespace nono

#include <algorithm>
#include <iterator>
#include <vector>

namespace nono {

template <class T>
class Compressor {
  public:
    Compressor() = default;

    Compressor(const std::vector<T>& data): data_(data) {
        std::sort(data_.begin(), data_.end());
        data_.erase(std::unique(data_.begin(), data_.end()), data_.end());
    }
    Compressor(std::vector<T>&& data): data_(data) {
        std::sort(data_.begin(), data_.end());
        data_.erase(std::unique(data_.begin(), data_.end()), data_.end());
    }

    int compress(const T& value) const {
        return std::distance(data_.begin(), std::lower_bound(data_.begin(), data_.end(), value));
    }

    std::vector<int> compress(const std::vector<T>& vec) const {
        std::vector<int> result(vec.size());
        for (int i = 0; auto v: vec) {
            result[i] = compress(v);
            i++;
        }
        return result;
    }

    T decompress(int i) const {
        return data_[i];
    }

    int size() const {
        return data_.size();
    }

    bool contains(const T& value) const {
        auto it = std::ranges::lower_bound(data_, value);
        return it != data_.end() && *it == value;
    }

  private:
    std::vector<T> data_;
};

}  //  namespace nono

#include <algorithm>
#include <vector>

namespace nono {

template <class T>
std::vector<std::vector<int>> strongly_connected_components(const Graph<T>& graph) {
    constexpr int NONE = -1;

    int n = graph.size();
    std::vector<int> order(n, NONE);
    std::vector<int> group_ids(n, NONE);
    std::vector<int> count(n);
    std::vector<int> history;
    history.reserve(n);

    int now = 0;
    int group_id = 0;

    auto dfs = [&](const auto& self, int u) -> int {
        int lowlink = order[u] = now++;
        history.push_back(u);

        for (const auto& edge: graph[u]) {
            if (order[edge.to] == NONE) {
                lowlink = std::min(lowlink, self(self, edge.to));
            } else if (group_ids[edge.to] == NONE) {
                lowlink = std::min(lowlink, order[edge.to]);
            }
        }

        if (lowlink == order[u]) {
            while (!history.empty()) {
                int v = history.back();
                if (order[v] < order[u]) break;
                history.pop_back();
                group_ids[v] = group_id;
                count[group_id]++;
            }
            group_id++;
        }

        return lowlink;
    };

    for (int i = 0; i < n; i++) {
        if (order[i] == NONE) {
            dfs(dfs, i);
        }
    }

    std::vector<std::vector<int>> groups(group_id);
    for (int i = 0; i < group_id; i++) {
        groups[group_id - i - 1].reserve(count[i]);
    }
    for (int i = 0; i < n; i++) {
        groups[group_id - group_ids[i] - 1].push_back(i);
    }
    return groups;
}

}  //  namespace nono

namespace nono {

void solve() {
    int n, a, b;
    std::cin >> n >> a >> b;
    std::vector<int> x(n);
    for (int i = 0; i < n; i++) std::cin >> x[i];
    Compressor compressor(x);
    std::vector<SegmentEdge<int>> edges;

    for (int i = 0; i < n; i++) {
        {
            int left = compressor.compress(x[i] + a);
            int right = compressor.compress(x[i] + b + 1);
            edges.emplace_back(std::pair(i, i + 1), std::pair(left, right), 1);
        }
        {
            int left = compressor.compress(x[i] - b);
            int right = compressor.compress(x[i] - a + 1);
            edges.emplace_back(std::pair(i, i + 1), std::pair(left, right), 1);
        }
    }
    auto [graph, mapping] = to_graph(n, edges);
    std::vector<int> ans(n);
    for (auto&& group: strongly_connected_components(graph)) {
        int count = 0;
        for (auto u: group) {
            if (mapping[u] != -1) count++;
        }
        for (auto u: group) {
            if (mapping[u] != -1) ans[mapping[u]] = count;
        }
    }
    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << '\n';
    }
}

}  //  namespace nono

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    nono::solve();
}

yukicoder

結果

テストケース

ソースコード