結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,820 KB
testcase_03 AC 95 ms
18,844 KB
testcase_04 AC 80 ms
17,084 KB
testcase_05 AC 66 ms
15,712 KB
testcase_06 AC 128 ms
22,832 KB
testcase_07 AC 142 ms
24,236 KB
testcase_08 AC 112 ms
24,156 KB
testcase_09 AC 120 ms
23,460 KB
testcase_10 AC 118 ms
24,152 KB
testcase_11 AC 88 ms
18,304 KB
testcase_12 AC 117 ms
24,000 KB
testcase_13 AC 80 ms
16,640 KB
testcase_14 AC 27 ms
13,568 KB
testcase_15 AC 156 ms
24,644 KB
testcase_16 AC 14 ms
7,040 KB
testcase_17 AC 129 ms
23,232 KB
testcase_18 AC 62 ms
13,696 KB
testcase_19 AC 21 ms
15,480 KB
testcase_20 AC 73 ms
15,744 KB
testcase_21 AC 35 ms
12,288 KB
testcase_22 AC 47 ms
18,408 KB
testcase_23 AC 152 ms
25,336 KB
testcase_24 AC 153 ms
25,288 KB
testcase_25 AC 133 ms
24,888 KB
testcase_26 AC 99 ms
24,584 KB
testcase_27 AC 124 ms
24,768 KB
権限があれば一括ダウンロードができます

ソースコード

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<int64_t>> bfs_shortest_path(const Graph<T> &g, const std::vector<int> &src){
  const int n = g.size();
  std::vector<std::optional<int64_t>> 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 = INT_MAX;
  
  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