結果
問題 | No.1190 Points |
ユーザー | risujiroh |
提出日時 | 2020-08-22 14:34:17 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 1,593 bytes |
コンパイル時間 | 2,723 ms |
コンパイル使用メモリ | 262,008 KB |
実行使用メモリ | 18,976 KB |
最終ジャッジ日時 | 2024-04-23 08:55:33 |
合計ジャッジ時間 | 5,380 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 48 ms
14,412 KB |
testcase_04 | AC | 39 ms
13,196 KB |
testcase_05 | AC | 37 ms
12,480 KB |
testcase_06 | AC | 67 ms
17,280 KB |
testcase_07 | AC | 71 ms
18,492 KB |
testcase_08 | AC | 64 ms
18,316 KB |
testcase_09 | AC | 75 ms
17,896 KB |
testcase_10 | AC | 71 ms
18,296 KB |
testcase_11 | AC | 55 ms
14,092 KB |
testcase_12 | AC | 70 ms
18,044 KB |
testcase_13 | AC | 47 ms
12,800 KB |
testcase_14 | AC | 14 ms
9,916 KB |
testcase_15 | AC | 80 ms
18,600 KB |
testcase_16 | AC | 9 ms
6,944 KB |
testcase_17 | AC | 70 ms
17,556 KB |
testcase_18 | AC | 42 ms
10,376 KB |
testcase_19 | AC | 11 ms
10,768 KB |
testcase_20 | AC | 47 ms
11,888 KB |
testcase_21 | AC | 18 ms
9,372 KB |
testcase_22 | AC | 25 ms
13,292 KB |
testcase_23 | AC | 82 ms
18,976 KB |
testcase_24 | AC | 81 ms
18,832 KB |
testcase_25 | AC | 51 ms
17,688 KB |
testcase_26 | AC | 52 ms
17,676 KB |
testcase_27 | AC | 52 ms
17,616 KB |
ソースコード
#include <bits/extc++.h> #ifndef DUMP #define DUMP(...) (void)0 #endif using namespace std; struct graph { struct edge { int src, dst; int operator-(int v) const { return src ^ dst ^ v; } }; int n, m; vector<edge> edges; vector<vector<pair<int, int>>> adj; graph(int _n = 0) : n(_n), m(0), adj(n) {} int add(const edge& e, bool directed = false) { edges.push_back(e); adj[e.src].emplace_back(m, e.dst); if (not directed) adj[e.dst].emplace_back(m, e.src); return m++; } }; vector<int> bfs(const graph& g, int s) { vector d(g.n, 0x3f3f3f3f); queue<int> que; d[s] = 0; que.push(s); while (not empty(que)) { int v = que.front(); que.pop(); for (auto [id, u] : g.adj[v]) if (d[u] == 0x3f3f3f3f) { d[u] = d[v] + 1; que.push(u); } } return d; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int n, m, p; cin >> n >> m >> p; int s, t; cin >> s >> t; --s, --t; graph g(n * 2); while (m--) { int u, v; cin >> u >> v; --u, --v; g.add({u * 2, v * 2 + 1}); g.add({u * 2 + 1, v * 2}); } auto ds = bfs(g, s * 2); if (ds[t * 2 + (p & 1)] > p) { cout << "-1\n"; exit(0); } auto dt = bfs(g, t * 2); vector<int> res; for (int v = 0; v < n; ++v) { for (int x : {0, 1}) { if (ds[v * 2 + x] + dt[v * 2 + ((p & 1) ^ x)] <= p) { res.push_back(v); break; } } } cout << size(res) << '\n'; for (auto&& e : res) cout << e + 1 << '\n'; }