結果
問題 | No.1190 Points |
ユーザー | AndrewK |
提出日時 | 2020-08-22 11:32:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 471 ms / 2,000 ms |
コード長 | 2,472 bytes |
コンパイル時間 | 1,918 ms |
コンパイル使用メモリ | 176,208 KB |
実行使用メモリ | 42,260 KB |
最終ジャッジ日時 | 2024-04-23 07:06:55 |
合計ジャッジ時間 | 10,451 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 12 ms
28,000 KB |
testcase_01 | AC | 12 ms
27,448 KB |
testcase_02 | AC | 12 ms
28,152 KB |
testcase_03 | AC | 274 ms
38,160 KB |
testcase_04 | AC | 196 ms
37,084 KB |
testcase_05 | AC | 234 ms
35,988 KB |
testcase_06 | AC | 301 ms
40,692 KB |
testcase_07 | AC | 403 ms
41,716 KB |
testcase_08 | AC | 339 ms
42,140 KB |
testcase_09 | AC | 351 ms
41,880 KB |
testcase_10 | AC | 337 ms
42,260 KB |
testcase_11 | AC | 249 ms
38,072 KB |
testcase_12 | AC | 325 ms
42,044 KB |
testcase_13 | AC | 267 ms
37,256 KB |
testcase_14 | AC | 68 ms
32,036 KB |
testcase_15 | AC | 466 ms
41,824 KB |
testcase_16 | AC | 50 ms
30,676 KB |
testcase_17 | AC | 406 ms
40,596 KB |
testcase_18 | AC | 234 ms
37,072 KB |
testcase_19 | AC | 43 ms
30,984 KB |
testcase_20 | AC | 289 ms
38,396 KB |
testcase_21 | AC | 89 ms
32,948 KB |
testcase_22 | AC | 124 ms
35,228 KB |
testcase_23 | AC | 456 ms
42,004 KB |
testcase_24 | AC | 471 ms
41,888 KB |
testcase_25 | AC | 329 ms
41,784 KB |
testcase_26 | AC | 306 ms
41,504 KB |
testcase_27 | AC | 348 ms
41,808 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; int N, M, P, S, G, u[100001], v[100001]; int kyo_s[100001][2], kyo_g[100001][2]; constexpr int inf = 1000000000; set<pair<int, int>> st; queue<pair<int, int>> q; vector<int> edge[1000001]; vector<int> ans; int main() { cin >> N >> M >> P; cin >> S >> G; assert(2 <= N && N <= 100000); long long lbig = min((long long)N * ((long long)N - 1ll) / 2ll, 100000ll); int big = lbig; assert(1 <= M && M <= big); assert(1 <= P && P <= 1000000000); assert(S != G); for (int i = 1; i <= M; i++) { cin >> u[i] >> v[i]; assert(u[i] != v[i]); assert(st.count(pair<int, int>(u[i], v[i])) == 0); st.insert(pair<int, int>(u[i], v[i])); st.insert(pair<int, int>(v[i], u[i])); edge[u[i]].push_back(v[i]); edge[v[i]].push_back(u[i]); } for (int i = 1; i <= N; i++) { kyo_s[i][0] = inf; kyo_s[i][1] = inf; kyo_g[i][0] = inf; kyo_g[i][1] = inf; } kyo_s[S][0] = 0; q.push(make_pair(0, S)); while (q.size()) { int cnt = q.front().first; int x = q.front().second; q.pop(); if (kyo_s[x][cnt % 2] < cnt) continue; cnt++; for (auto &i : edge[x]) { if (kyo_s[i][cnt % 2] > cnt) { kyo_s[i][cnt % 2] = cnt; q.push(make_pair(cnt, i)); } } } kyo_g[G][0] = 0; q.push(make_pair(0, G)); while (q.size()) { int cnt = q.front().first; int x = q.front().second; q.pop(); if (kyo_g[x][cnt % 2] < cnt) continue; cnt++; for (auto &i : edge[x]) { if (kyo_g[i][cnt % 2] > cnt) { kyo_g[i][cnt % 2] = cnt; q.push(make_pair(cnt, i)); } } } for (int i = 1; i <= N; i++) { if (P % 2) { int odd = min(kyo_s[i][0] + kyo_g[i][1], kyo_s[i][1] + kyo_g[i][0]); if (odd <= P) { ans.push_back(i); } } else { int even = min(kyo_s[i][0] + kyo_g[i][0], kyo_s[i][1] + kyo_g[i][1]); if (even <= P) { ans.push_back(i); } } } if (ans.size() == 0) { cout << -1 << endl; return 0; } cout << ans.size() << endl; for (int i = 0; i < ans.size(); i++) { cout << ans[i] << endl; } return 0; }