結果

問題 No.1190 Points
ユーザー HaarHaar
提出日時 2020-08-25 00:21:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,812 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 217,336 KB
実行使用メモリ 22,220 KB
最終ジャッジ日時 2024-11-06 10:54:59
合計ジャッジ時間 6,163 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 84 ms
16,512 KB
testcase_04 AC 68 ms
14,928 KB
testcase_05 AC 60 ms
13,952 KB
testcase_06 AC 120 ms
19,884 KB
testcase_07 AC 129 ms
21,260 KB
testcase_08 AC 100 ms
21,112 KB
testcase_09 AC 113 ms
20,832 KB
testcase_10 AC 106 ms
21,028 KB
testcase_11 AC 83 ms
16,580 KB
testcase_12 AC 108 ms
20,924 KB
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 -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T>
auto make_vector(int n, int m, const T &value){
  return std::vector<std::vector<T>>(n, std::vector<T>(m, value));
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}


/**
 * @title Graph template
 * @docs graph_template.md
 */
template <typename Cost = int> class Edge{
public:
  int from,to;
  Cost cost;
  Edge() {}
  Edge(int to, Cost cost): to(to), cost(cost){}
  Edge(int from, int to, Cost cost): from(from), to(to), cost(cost){}
};

template <typename T> using Graph = std::vector<std::vector<Edge<T>>>;
template <typename T> using Tree = std::vector<std::vector<Edge<T>>>;

template <typename T, typename C> void add_edge(C &g, int from, int to, T w = 1){
  g[from].emplace_back(from, to, w);
}

template <typename T, typename C> void add_undirected(C &g, int a, int b, T w = 1){
  add_edge<T, C>(g, a, b, w);
  add_edge<T, C>(g, b, a, w);
}


/**
 * @title BFS shortest path
 * @docs bfs_shortest_path.md
 */
template <typename T>
std::vector<std::optional<int>> bfs_shortest_path(const Graph<T> &g, const std::vector<int> &src){
  const int n = g.size();
  std::vector<std::optional<int>> ret(n, std::nullopt);
  std::vector<bool> visited(n);
  std::queue<int> q;

  for(auto s : src){
    ret[s] = 0;
    q.push(s);
  }

  while(not q.empty()){
    const int cur = q.front(); q.pop();

    if(visited[cur]) continue;
    visited[cur] = true;

    for(auto &e : g[cur]){
      if(not ret[e.to] or *ret[e.to] > *ret[e.from] + 1){
        ret[e.to] = *ret[e.from] + 1;
        q.push(e.to);
      }
    }
  }

  return ret;
}


namespace solver{
  constexpr int INF = 10000000;
  
  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }
  
  void solve(){
    int N, M, P; std::cin >> N >> M >> P;
    int S, G; std::cin >> S >> G;
    --S, --G;

    Graph<int64_t> g(2 * N);

    for(int i = 0; i < M; ++i){
      int u, v; std::cin >> u >> v;
      --u, --v;
      add_undirected(g, u, v + N, 1);
      add_undirected(g, u + N, v, 1);
    }

    auto s_dist = bfs_shortest_path(g, {S});
    auto g_dist = bfs_shortest_path(g, {G});

    std::vector<int> ans;
    for(int i = 0; i < N; ++i){
      bool ok = false;

      if(P % 2 == 0){
        if(s_dist[i].value_or(INF) + g_dist[i].value_or(INF) <= P or
           s_dist[i + N].value_or(INF) + g_dist[i + N].value_or(INF) <= P){
          ok = true;
        }
      }else{
        if(s_dist[i].value_or(INF) + g_dist[i + N].value_or(INF) <= P or
           s_dist[i + N].value_or(INF) + g_dist[i].value_or(INF) <= P){
          ok = true;
        }
      }

      if(ok) ans.push_back(i + 1);
    }

    if(ans.empty()) std::cout << -1 << "\n";
    else{
      std::cout << ans.size() << "\n";
      for(auto x : ans) std::cout << x << "\n";
    }
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
    }catch(const std::istream::failure &e){
      break;
    }
  }
  return 0;
}
0