結果
| 問題 | No.1477 Lamps on Graph |
| ユーザー |
 hirono999
|
| 提出日時 | 2021-04-16 20:27:41 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,924 bytes |
| コンパイル時間 | 3,762 ms |
| コンパイル使用メモリ | 234,352 KB |
| 実行使用メモリ | 12,168 KB |
| 最終ジャッジ日時 | 2024-07-02 22:44:44 |
| 合計ジャッジ時間 | 12,268 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
ソースコード
#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 : ret) print(r);
return 0;
}