結果
| 問題 | No.2780 The Bottle Imp |
| ユーザー |
 cutmdo
|
| 提出日時 | 2024-12-19 14:49:15 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 17,867 bytes |
| コンパイル時間 | 2,472 ms |
| コンパイル使用メモリ | 186,572 KB |
| 実行使用メモリ | 26,372 KB |
| 最終ジャッジ日時 | 2024-12-19 14:49:21 |
| 合計ジャッジ時間 | 5,122 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,816 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
| testcase_04 | AC | 1 ms
6,820 KB |
| testcase_05 | AC | 1 ms
6,820 KB |
| testcase_06 | AC | 2 ms
6,816 KB |
| testcase_07 | AC | 47 ms
11,392 KB |
| testcase_08 | AC | 44 ms
11,392 KB |
| testcase_09 | AC | 45 ms
11,392 KB |
| testcase_10 | AC | 46 ms
11,520 KB |
| testcase_11 | AC | 47 ms
11,392 KB |
| testcase_12 | AC | 84 ms
17,644 KB |
| testcase_13 | AC | 88 ms
17,652 KB |
| testcase_14 | AC | 24 ms
11,008 KB |
| testcase_15 | AC | 25 ms
10,880 KB |
| testcase_16 | AC | 26 ms
11,136 KB |
| testcase_17 | AC | 26 ms
10,880 KB |
| testcase_18 | AC | 25 ms
10,880 KB |
| testcase_19 | AC | 25 ms
10,880 KB |
| testcase_20 | AC | 25 ms
10,880 KB |
| testcase_21 | AC | 25 ms
10,880 KB |
| testcase_22 | AC | 16 ms
6,912 KB |
| testcase_23 | AC | 21 ms
9,600 KB |
| testcase_24 | AC | 36 ms
10,112 KB |
| testcase_25 | AC | 70 ms
14,572 KB |
| testcase_26 | AC | 33 ms
10,752 KB |
| testcase_27 | AC | 21 ms
11,280 KB |
| testcase_28 | AC | 19 ms
11,288 KB |
| testcase_29 | AC | 29 ms
11,516 KB |
| testcase_30 | AC | 24 ms
9,396 KB |
| testcase_31 | AC | 33 ms
15,192 KB |
| testcase_32 | AC | 13 ms
9,600 KB |
| testcase_33 | AC | 42 ms
24,272 KB |
| testcase_34 | AC | 69 ms
26,372 KB |
| testcase_35 | AC | 12 ms
7,808 KB |
| testcase_36 | AC | 2 ms
6,820 KB |
| testcase_37 | AC | 1 ms
6,820 KB |
| testcase_38 | AC | 11 ms
7,808 KB |
| testcase_39 | AC | 33 ms
16,528 KB |
| testcase_40 | AC | 31 ms
16,276 KB |
| testcase_41 | AC | 32 ms
16,272 KB |
| testcase_42 | WA | - |
| testcase_43 | AC | 2 ms
6,816 KB |
ソースコード
#include <vector>
#define PROBLEM "https://yukicoder.me/problems/no/2780"
#include <iostream>
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <unordered_set>
#include <deque>
#include <tuple>
#include <set>
#include <ranges>
namespace mtd { template <class Node = int, class Cost = long long> class Graph { using Edge = std::pair<Node, Cost>; using Edges = std::vector<Edge>; const int m_n; std::vector<Edges> m_graph; public: Graph(int n) : m_n(n), m_graph(n) {} Graph(const std::vector<Edges>& edges) : m_n(edges.size()), m_graph(edges) {} auto addEdge(const Node& f, const Node& t, const Cost& c = 1) { m_graph[f].emplace_back(t, c); } auto addEdgeUndirected(const Node& f, const Node& t, const Cost& c = 1) { addEdge(f, t, c); addEdge(t, f, c); } auto getEdges(const Node& from) const { class EdgesRange { const typename Edges::const_iterator b, e; public: EdgesRange(const Edges& edges) : b(edges.begin()), e(edges.end()) {} auto begin() const { return b; } auto end() const { return e; } }; return EdgesRange(m_graph[from]); } auto getEdges() const { std::deque<std::tuple<Node, Node, Cost>> edges; for (Node from : std::views::iota(0, m_n)) { for (const auto& [to, c] : getEdges(from)) { edges.emplace_back(from, to, c); } } return edges; } auto getEdgesExcludeCost() const { std::deque<std::pair<Node, Node>> edges; for (Node from : std::views::iota(0, m_n)) { for (const auto& [to, _] : getEdges(from)) { edges.emplace_back(from, to); } } return edges; } auto reverse() const { auto rev = Graph<Node, Cost>(m_n); for (const auto& [from, to, c] : getEdges()) { rev.addEdge(to, from, c); } return rev; } auto size() const { return m_n; }; auto debug(bool directed = false) const { for (const auto& [f, t, c] : getEdges()) { if (f < t || directed) { std::cout << f << " -> " << t << ": " << c << std::endl; } } } };}
namespace mtd { namespace util { template <class F, class T> constexpr auto tuple_transform(F&& f, T&& t) { return std::apply( [&]<class... Ts>(Ts&&... elems) { return std::tuple<std::invoke_result_t<F&, Ts>...>( std::invoke(f, std::forward<Ts>(elems))...); }, std::forward<T>(t)); } template <class F, class T> constexpr auto tuple_for_each(F&& f, T&& t) { std::apply( [&]<class... Ts>(Ts&&... elems) { (std::invoke(f, std::forward<Ts>(elems)), ...); }, std::forward<T>(t)); } } }
namespace mtd { template <class Node, class Cost> class StronglyConnectedComponents { struct HashPair { template <class T1, class T2> size_t operator()(const std::pair<T1, T2>& p) const { auto hash1 = std::hash<T1>{}(p.first); auto hash2 = std::hash<T2>{}(p.second); size_t seed = 0; seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; const Graph<Node, Cost> m_graph; const std::vector<int> m_group; template <class F> constexpr static inline auto dfs(const Graph<Node, Cost>& graph, int from, std::vector<bool>& is_used, const F& f) -> void { is_used[from] = true; for (const auto& [to, _] : graph.getEdges(from)) { if (is_used[to]) { continue; } dfs(graph, to, is_used, f); } f(from); } constexpr static auto constructGroup(const Graph<Node, Cost>& graph) { int n = graph.size(); std::vector<Node> order; std::vector<bool> is_used(n); for (auto from : std::views::iota(0, n)) { if (is_used[from]) { continue; } dfs(graph, from, is_used, [&](int f) { order.emplace_back(f); }); } int g = 0; std::vector<Node> group(n); std::vector<bool> is_used2(n); auto rev = graph.reverse(); for (auto from : order | std::views::reverse) { if (is_used2[from]) { continue; } dfs(rev, from, is_used2, [&](int f) { group[f] = g; }); ++g; } return group; } public: [[deprecated]] constexpr StronglyConnectedComponents( const Graph<Node, Cost>& graph) : m_graph(graph), m_group(constructGroup(m_graph)) {} constexpr StronglyConnectedComponents(Graph<Node, Cost>&& graph) : m_graph(std::move(graph)), m_group(constructGroup(m_graph)) {} constexpr auto size() const { return *std::max_element(m_group.begin(), m_group.end()) + 1; } constexpr auto group(int a) const { return m_group[a]; } constexpr auto isSameGroup(int a, int b) const { return m_group[a] == m_group[b]; } constexpr auto getGroupNodes() const { std::vector<std::vector<int>> groupNodes(size()); for (int gi = 0; gi < m_graph.size(); ++gi) { groupNodes[m_group[gi]].emplace_back(gi); } return groupNodes; } constexpr auto getGroupGraph() const { std::unordered_set<std::pair<int, int>, HashPair> st; st.reserve(m_graph.size()); for (int f = 0; f < m_graph.size(); ++f) { for (const auto& [t, _] : m_graph.getEdges(f)) { if (!isSameGroup(f, t)) { st.emplace(m_group[f], m_group[t]); } } } Graph<Node, Cost> ret(size()); for (const auto& [f, t] : st) { ret.addEdge(f, t); } return ret; } };}
namespace mtd { namespace ranges { namespace __detail { template <typename... T> concept __all_random_access = (std::ranges::random_access_range<T> && ...); template <typename... T> concept __all_bidirectional = (std::ranges::bidirectional_range<T> && ...); template <typename... T> concept __all_forward = (std::ranges::forward_range<T> && ...); template <class... T> constexpr auto _S_iter_concept() { if constexpr (__all_random_access<T...>) { return std::random_access_iterator_tag{}; } else if constexpr (__all_bidirectional<T...>) { return std::bidirectional_iterator_tag{}; } else if constexpr (__all_forward<T...>) { return std::forward_iterator_tag{}; } else { return std::input_iterator_tag{}; } } } template <std::ranges::range... _Range> struct zip_view : public std::ranges::view_interface<zip_view<_Range...>> { class iterator { public: std::tuple<std::ranges::iterator_t<_Range>...> _M_current; using difference_type = int; using value_type = std::tuple< std::iter_reference_t<std::ranges::iterator_t<_Range>>...>; using iterator_concept = decltype(__detail::_S_iter_concept<_Range...>()); constexpr iterator() = default; constexpr explicit iterator(const decltype(_M_current)& __current) : _M_current(__current) {} constexpr auto operator*() const { return util::tuple_transform([](auto& __i) { return *__i; }, _M_current); } constexpr auto& operator++() { util::tuple_for_each([](auto& __i) { ++__i; }, _M_current); return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& other) const { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return ((std::get<_Is>(_M_current) == std::get<_Is>(other._M_current)) || ...); } (std::make_index_sequence<sizeof...(_Range)>{}); } constexpr auto& operator--() requires __detail::__all_bidirectional<_Range...> { util::tuple_for_each([](auto& __i) { --__i; }, _M_current); return *this; } constexpr auto operator--( int) requires __detail::__all_bidirectional<_Range...> { return --*this; } constexpr auto operator<=>(const iterator&) const requires __detail::__all_random_access<_Range...> = default; constexpr auto operator-(const iterator& itr) const requires __detail::__all_random_access<_Range...> { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return std::ranges::min({difference_type( std::get<_Is>(_M_current) - std::get<_Is>(itr._M_current))...}); } (std::make_index_sequence<sizeof...(_Range)>{}); } constexpr auto& operator+=(const difference_type n) requires __detail::__all_random_access<_Range...> { util::tuple_for_each([&n](auto& __i) { __i += n; }, _M_current); return *this; } constexpr auto operator+(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __r = *this; __r += n; return __r; } constexpr friend auto operator+(const difference_type n, const iterator& itr) requires __detail::__all_random_access<_Range...> { return itr + n; } constexpr auto& operator-=(const difference_type n) requires __detail::__all_random_access<_Range...> { util::tuple_for_each([&n](auto& __i) { __i -= n; }, _M_current); return *this; } constexpr auto operator-(const difference_type n) const requires __detail::__all_random_access<_Range...> { auto __r = *this; __r -= n; return __r; } constexpr auto operator[](const difference_type n) const requires __detail::__all_random_access<_Range...> { return util::tuple_transform([&n](auto& __i) { return __i[n]; }, _M_current); } }; class sentinel { public: std::tuple<std::ranges::sentinel_t<_Range>...> _M_end; constexpr sentinel() = default; constexpr explicit sentinel(const decltype(_M_end)& __end) : _M_end(__end) {} friend constexpr bool operator==(const iterator& __x, const sentinel& __y) { return [&]<size_t... _Is>(std::index_sequence<_Is...>) { return ( (std::get<_Is>(__x._M_current) == std::get<_Is>(__y._M_end)) || ...); } (std::make_index_sequence<sizeof...(_Range)>{}); } }; std::tuple<_Range...> __r; constexpr explicit zip_view(const _Range&... __r) : __r(__r...) {} constexpr auto begin() { return iterator(util::tuple_transform(std::ranges::begin, __r)); } constexpr auto end() { return sentinel(util::tuple_transform(std::ranges::end, __r)); } }; namespace __detail { template <typename T> auto _flatten(const T& t) { return std::make_tuple(t); } template <typename... T> auto _flatten(const std::tuple<T...>& t); template <typename Head, typename... Tail> auto _flatten_impl(const Head& head, const Tail&... tail) { return std::tuple_cat(_flatten(head), _flatten(tail)...); } template <typename... T> auto _flatten(const std::tuple<T...>& t) { return std::apply( [](const auto&... args) { return _flatten_impl(args...); }, t); } } template <std::ranges::range _Range> struct flatten_view : public std::ranges::view_interface<flatten_view<_Range>> { class iterator { public: std::ranges::iterator_t<_Range> _M_current; using difference_type = std::ranges::range_difference_t<_Range>; using value_type = decltype(__detail::_flatten( std::declval< std::iter_reference_t<std::ranges::iterator_t<_Range>>>())); using iterator_concept = decltype(__detail::_S_iter_concept<_Range>()); constexpr iterator() = default; constexpr explicit iterator(decltype(_M_current) __current) : _M_current(__current) {} constexpr auto operator*() const { return __detail::_flatten(*_M_current); } constexpr auto& operator++() { ++_M_current; return *this; } constexpr auto operator++(int) { return ++*this; } constexpr auto operator==(const iterator& other) const { return _M_current == other._M_current; } constexpr auto& operator--() requires __detail::__all_bidirectional<_Range> { --_M_current; return *this; } constexpr auto operator--( int) requires __detail::__all_bidirectional<_Range> { return --*this; } constexpr auto operator<=>(const iterator&) const requires __detail::__all_random_access<_Range> = default; constexpr auto operator-(const iterator& itr) const requires __detail::__all_random_access<_Range> { return _M_current - itr._M_current; } constexpr auto& operator+=(const difference_type n) requires __detail::__all_random_access<_Range> { _M_current += n; return *this; } constexpr auto operator+(const difference_type n) const requires __detail::__all_random_access<_Range> { auto __r = *this; __r += n; return __r; } constexpr friend auto operator+(const difference_type n, const iterator& itr) requires __detail::__all_random_access<_Range> { return itr + n; } constexpr auto& operator-=(const difference_type n) requires __detail::__all_random_access<_Range> { _M_current -= n; return *this; } constexpr auto operator-(const difference_type n) const requires __detail::__all_random_access<_Range> { auto __r = *this; __r -= n; return __r; } constexpr auto operator[](const difference_type n) const requires __detail::__all_random_access<_Range> { return __detail::_flatten(_M_current[n]); } }; class sentinel { std::ranges::sentinel_t<_Range> _M_end; public: constexpr sentinel() = default; constexpr explicit sentinel(const decltype(_M_end)& __end) : _M_end(__end) {} friend constexpr bool operator==(const iterator& __x, const sentinel& __y) { return __x._M_current == __y._M_end; } }; _Range __r; constexpr explicit flatten_view(const _Range& __r) : __r(__r) {} constexpr auto begin() { return iterator(std::ranges::begin(__r)); } constexpr auto end() { return sentinel(std::ranges::end(__r)); } }; } namespace views { namespace __detail { template <typename... _Args> concept __can_zip_view = requires { ranges::zip_view(std::declval<_Args>()...); }; template <typename... _Args> concept __can_flatten_view = requires { ranges::flatten_view(std::declval<_Args>()...); }; } struct _ZipView { template <class... _Tp> requires __detail::__can_zip_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::zip_view(std::forward<_Tp>(__e)...); } }; struct _Enumerate : std::views::__adaptor::_RangeAdaptorClosure { template <class _Tp> requires __detail::__can_zip_view<std::ranges::iota_view<size_t>, _Tp> constexpr auto operator() [[nodiscard]] (_Tp&& __e) const { return ranges::zip_view{std::views::iota(0), std::forward<_Tp>(__e)}; } static constexpr bool _S_has_simple_call_op = true; }; struct _Flatten : std::views::__adaptor::_RangeAdaptorClosure { template <class... _Tp> requires __detail::__can_flatten_view<_Tp...> constexpr auto operator() [[nodiscard]] (_Tp&&... __e) const { return ranges::flatten_view(std::forward<_Tp>(__e)...); } static constexpr bool _S_has_simple_call_op = true; }; inline constexpr _ZipView zip{}; inline constexpr _Enumerate enumerate{}; inline constexpr _Flatten flatten{}; } }
namespace mtd { template <class Node, class Cost> auto topological_order(const mtd::Graph<Node, Cost>& graph) { std::vector<Node> cnt(graph.size()); for (auto [_, v] : graph.getEdgesExcludeCost()) { ++cnt[v]; } std::deque<Node> q; for (auto [nd, c] : cnt | mtd::views::enumerate) { if (c == 0) { q.emplace_back(nd); } } std::vector<Node> order; while (!q.empty()) { auto nd = q.front(); q.pop_front(); order.emplace_back(nd); for (auto [v, _] : graph.getEdges(nd)) { --cnt[v]; if (cnt[v] == 0) { q.emplace_back(v); } } } return order; }}
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
int n;
std::cin >> n;
auto graph = mtd::Graph<>(n);
for (auto u : std::views::iota(0, n)) {
int m;
std::cin >> m;
for ([[maybe_unused]] auto _ : std::views::iota(0, m)) {
int v;
std::cin >> v;
graph.addEdge(u, v - 1);
}
}
auto scc = mtd::StronglyConnectedComponents(std::move(graph));
auto scc_graph = scc.getGroupGraph();
auto size = scc.size();
std::vector<int> p(size, true);
std::vector<int> dp(size);
dp[scc.group(0)] = true;
for (auto u : mtd::topological_order(scc_graph)) {
for (auto [v, _] : scc_graph.getEdges(u)) {
dp[v] |= dp[u] & p[u];
p[u] = false;
}
}
auto yes = std::ranges::all_of(dp, [](int x) { return x; });
std::cout << (yes ? "Yes" : "No") << std::endl;
}