結果
問題 | No.1477 Lamps on Graph |
ユーザー | hirono999 |
提出日時 | 2021-04-16 20:31:17 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 9,924 bytes |
コンパイル時間 | 3,589 ms |
コンパイル使用メモリ | 233,396 KB |
実行使用メモリ | 12,296 KB |
最終ジャッジ日時 | 2024-07-02 22:50:22 |
合計ジャッジ時間 | 7,138 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | AC | 40 ms
7,808 KB |
testcase_13 | AC | 36 ms
7,272 KB |
testcase_14 | AC | 51 ms
8,480 KB |
testcase_15 | AC | 24 ms
6,940 KB |
testcase_16 | AC | 14 ms
6,940 KB |
testcase_17 | AC | 13 ms
6,944 KB |
testcase_18 | AC | 34 ms
9,264 KB |
testcase_19 | AC | 32 ms
7,472 KB |
testcase_20 | AC | 15 ms
6,940 KB |
testcase_21 | AC | 29 ms
7,980 KB |
testcase_22 | AC | 10 ms
6,944 KB |
testcase_23 | AC | 29 ms
6,940 KB |
testcase_24 | AC | 56 ms
9,040 KB |
testcase_25 | AC | 20 ms
6,944 KB |
testcase_26 | AC | 48 ms
9,288 KB |
testcase_27 | AC | 27 ms
6,940 KB |
testcase_28 | AC | 31 ms
7,040 KB |
testcase_29 | AC | 29 ms
6,940 KB |
testcase_30 | AC | 17 ms
6,940 KB |
testcase_31 | AC | 15 ms
6,940 KB |
testcase_32 | AC | 54 ms
12,296 KB |
testcase_33 | AC | 52 ms
11,804 KB |
testcase_34 | AC | 46 ms
9,300 KB |
testcase_35 | AC | 69 ms
11,200 KB |
testcase_36 | AC | 67 ms
11,196 KB |
testcase_37 | AC | 59 ms
11,008 KB |
testcase_38 | AC | 63 ms
11,080 KB |
testcase_39 | AC | 73 ms
11,204 KB |
ソースコード
#line 2 "/home/snow/competitive-programming/competitive-programming-library/snow/template.hpp" #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> constexpr long long INF = 1LL << 60; constexpr long double PI = 3.141592653589; #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rep1(i, n) for (ll i = 1; i <= (n); ++i) #define rrep(i, n) for (ll i = (n - 1); i >= 0; --i) #define ALL(obj) (obj).begin(), (obj).end() #define RALL(obj) (obj).rbegin(), (obj).rend() #define pb push_back #define to_s to_string #define len(v) (ll) v.size() #define debug(x) cout << #x << ": " << (x) << '\n' using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> P; typedef tuple<ll, ll, ll> tpl; template <typename T = ll> using vec = vector<T>; template <typename T = ll> using vec2 = vector<vector<T>>; template <typename T = ll> using vec3 = vector<vector<vector<T>>>; template < typename T > inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template < typename T > inline bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } #line 4 "/home/snow/competitive-programming/competitive-programming-library/snow/io/setup.hpp" namespace snow{ struct IoSetup { IoSetup() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(10); } } iosetup; } #line 5 "/home/snow/competitive-programming/competitive-programming-library/snow/io/helper.hpp" template< typename T1, typename T2 > std::ostream &operator << (std::ostream &os, const std::pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > std::istream &operator >> (std::istream &is, std::pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T1, typename T2, typename T3 > std::ostream &operator << (std::ostream &os, const std::tuple< T1, T2, T3 > &t) { auto &[a, b, c] = t; os << a << " " << b << " " << c; return os; } template< typename T1, typename T2, typename T3 > std::istream &operator >> (std::istream &is, std::tuple< T1, T2, T3 > &t) { auto &[a, b, c] = t; is >> a >> b >> c; return is; } template< typename T > std::ostream &operator << (std::ostream &os, const std::vector< T > &v){ for (int i = 0; i < (int)v.size(); ++i) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > std::istream &operator >> (std::istream &is, std::vector< T > &v){ for(T &in : v) is >> in; return is; } template< typename T > std::ostream &operator << (std::ostream &os, const std::set< T > &st){ int ct = 0; for(auto& s : st) os << s << (++ct != st.size() ? " " : ""); return os; } template<class... T> void input(T&... a){ (std::cin >> ... >> a); } void print() { std::cout << '\n'; } template<class T, class... Ts> void print(const T& a, const Ts&... b){ std::cout << a; (std::cout << ... << (std::cout << ' ', b)); std::cout << '\n'; } int drop() { std::cout << '\n'; exit(0); } template<class T, class... Ts> int drop(const T& a, const Ts&... b){ std::cout << a; (std::cout << ... << (std::cout << ' ', b)); std::cout << '\n'; exit(0); } #line 4 "main.cpp" using namespace snow; // #include "snow/algorithm/binary-search.hpp" // #include "atcoder/modint" // using namespace atcoder; // using mint = modint1000000007; #line 2 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/graph" #line 2 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/template.hpp" #line 5 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/template.hpp" namespace snow { /** * @brief Graph template */ template < typename T > struct Graph { struct Edge { int to; T weight; Edge() : to(0), weight(0) {} Edge(int to, T weight) : to(to), weight(weight) {} }; using Edges = std::vector<Edge>; const T INF = std::numeric_limits<T>::max(); std::vector<Edges> G; Graph() : G() {} Graph(int n) : G(n) {} Edges& operator[](int k) { return G[k]; } const Edges& operator[](int k) const { return G[k]; } size_t size() const{ return G.size(); } void add_edge(int a, int b, T w = 1){ G[a].emplace_back(b, w); G[b].emplace_back(a, w); } void add_directed_edge(int a, int b, T w = 1){ G[a].emplace_back(b, w); } void add_arrow(int a, int b, T w = 1){ add_directed_edge(a, b, w); } //Dijkstra std::vector<T> dijkstra(int s) const; //Bellman-Ford std::vector<T> bellman_ford(int s) const; //Warshall-Floyd std::vector<std::vector<T>> warshall_floyd() const; //Topological sort std::vector<int> topological_sort() const; }; } // namespace snow #line 2 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/bellman-ford.hpp" #line 4 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/bellman-ford.hpp" #line 6 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/bellman-ford.hpp" namespace snow{ /** * @brief Bellman-Ford * * @param s */ template < typename T > std::vector<T> Graph<T>::bellman_ford(int s) const{ std::vector<T> dist(G.size(), INF); dist[s] = 0; for(int i = 0; i < (int)G.size(); ++i){ for(int j = 0; j < (int)G.size(); ++j){ for(auto& e : G[j]){ if(dist[j] == INF) continue; if(dist[e.to] > dist[j] + e.weight){ dist[e.to] = dist[j] + e.weight; if(i == ((int)G.size() - 1)) return {}; } } } } return dist; } } #line 2 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/dijkstra.hpp" #line 5 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/dijkstra.hpp" #line 7 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/dijkstra.hpp" namespace snow{ /** * @brief Dijkstra * * @param s */ template < typename T > std::vector<T> Graph<T>::dijkstra(int s) const{ std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<>> que; std::vector<T> dist(G.size(), INF); dist[s] = 0; que.emplace(dist[s], s); while(!que.empty()){ auto [cost, idx] = que.top(); que.pop(); if(dist[idx] < cost) continue; for(auto &e : G[idx]){ auto next_cost = cost + e.weight; if(dist[e.to] <= next_cost) continue; dist[e.to] = next_cost; que.emplace(dist[e.to], e.to); } } return dist; } } #line 2 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/warshall-floyd.hpp" #line 4 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/warshall-floyd.hpp" #line 6 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/shortest-path/warshall-floyd.hpp" namespace snow{ /** * @brief Warshall-Floyd * * @tparam T */ template < typename T > std::vector<std::vector<T>> Graph<T>::warshall_floyd() const{ int N = G.size(); std::vector<std::vector<T>> d(N, std::vector<T>(N, INF)); for(int i = 0; i < N; ++i) d[i][i] = 0; for(int i = 0; i < N; ++i) for(auto &e : G[i]) d[i][e.to] = e.weight; for(int k = 0; k < N; ++k){ for(int i = 0; i < N; ++i){ for(int j = 0; j < N; ++j){ if(d[i][k] == INF or d[k][j] == INF) continue; d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]); } } } return d; } } #line 2 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/topological-sort.hpp" #line 5 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/topological-sort.hpp" #line 7 "/home/snow/competitive-programming/competitive-programming-library/snow/graph/topological-sort.hpp" namespace snow { /** * @brief Topological Sort * */ template < typename T > std::vector<int> Graph<T>::topological_sort() const { int N = G.size(); std::vector<int> ind(N, 0); for(int i = 0; i < N; ++i) for (auto &e : G[i]) ind[e.to]++; std::queue<int> que; for(int i = 0; i < N; ++i) if (ind[i] == 0) que.push(i); std::vector<int> ans; while(!que.empty()){ int now = que.front(); que.pop(); ans.emplace_back(now); for(auto& e : G[now]) { ind[e.to]--; if(ind[e.to] == 0) que.push(e.to); } } if ((int)ans.size() != N) return {}; return ans; } } #line 13 "main.cpp" int main() { ll N, M; cin >> N >> M; vec<> A(N); cin >> A; Graph<ll> G(N); rep(i, M){ ll u, v; cin >> u >> v; --u, --v; if(A[u] < A[v]) G.add_directed_edge(u, v); if(A[u] > A[v]) G.add_directed_edge(v, u); } ll K; cin >> K; vec<> state(N); rep(i, K){ ll b; cin >> b; --b; state[b] = 1; } auto ret = G.topological_sort(); ll ans = 0; vec<> res; for(auto r : ret){ if(state[r]){ ++ans, res.pb(r + 1); state[r] = 0; for(auto e : G[r]) state[e.to] = !state[e.to]; } } rep(i, N){ if(state[i]) drop(-1); } print(ans); for(auto r : res) print(r); return 0; }