結果
問題 |
No.1190 Points
|
ユーザー |
|
提出日時 | 2023-04-23 11:23:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,216 bytes |
コンパイル時間 | 4,794 ms |
コンパイル使用メモリ | 201,204 KB |
最終ジャッジ日時 | 2025-02-12 13:21:00 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 15 |
ソースコード
#include <bits/stdc++.h> using namespace std; using Graph = vector<vector<int>>; int d[2][101010]; int d2[2][101010]; void dfs(Graph &g, int c, int v){ for (int i : g[v]){ if (d[c % 2][i] > c + 1){ d[c % 2][i] = c + 1; dfs(g, c + 1, i); } } } void dfs2(Graph &g, int c, int v){ for (int i : g[v]){ if (d2[c % 2][i] > c + 1){ d2[c % 2][i] = c + 1; dfs2(g, c + 1, i); } } } int main() { int n, m, p; cin >> n >> m >> p; int S, G; cin >> S >> G; S--; G--; Graph g(n); for (int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } for (int i = 0; i < 2; i++){ for (int j = 0; j < n; j++){ d[i][j] = 1 << 30; d2[i][j] = 1 << 30; } } d[0][S] = 0; dfs(g, 0, S); d2[0][G] = 0; dfs2(g, 0, G); set<int> ans; for (int i = 0; i < n; i++){ for (int j = 0; j < 2; j++){ for (int k = 0; k < 2; k++){ if (d[j][i] == (1 << 30) or d2[k][i] == (1 << 30)){ continue; } int c = p - d[j][i] - d2[k][i]; if (c >= 0 and c % 2 == 0){ ans.insert(i); } } } } if (ans.empty()){ cout << -1 << endl; return 0; } cout << ans.size() << endl; for (int i : ans){ cout << i + 1 << endl; } }