結果
問題 |
No.2948 move move rotti
|
ユーザー |
![]() |
提出日時 | 2024-10-25 21:49:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 400 ms / 4,000 ms |
コード長 | 1,743 bytes |
コンパイル時間 | 1,203 ms |
コンパイル使用メモリ | 91,044 KB |
最終ジャッジ日時 | 2025-02-24 22:59:19 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream> #include <iomanip> #include <cassert> #include <vector> int main() { std::cin.tie(nullptr)->sync_with_stdio(false); int N, M, K; std::cin >> N >> M >> K; std::vector<int> X(K); for (auto& x : X) { std::cin >> x; x--; } std::vector<std::vector<int>> g(N); for (int i{} ; i < M ; i++) { int u, v; std::cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } // u -> vへi歩 std::vector ok(N, std::vector(N, std::vector<bool>(N + 1))); std::vector dp(N, std::vector(N, std::vector<bool>(1 << N))); for (int i{} ; i < N ; i++) { dp[i][i][1 << i] = true; ok[i][i][0] = true; } for (int i{1} ; i <= N ; i++) { std::vector next(N, std::vector(N, std::vector<bool>(1 << N))); for (int bit{} ; bit < (1 << N) ; bit++) { for (int s{} ; s < N ; s++) for (int t{} ; t < N ; t++) { if (!dp[s][t][bit]) continue; for (auto v : g[t]) { if (bit & (1 << v)) continue; next[s][v][bit | (1 << v)] = true; } } } dp = std::move(next); for (int bit{} ; bit < (1 << N) ; bit++) { for (int s{} ; s < N ; s++) for (int t{} ; t < N ; t++) { if (dp[s][t][bit]) ok[s][t][i] = true; } } } for (int i{} ; i <= N ; i++) { for (int t{} ; t < N ; t++) { bool can{true}; for (auto x : X) can &= ok[x][t][i]; if (can) { std::cout << "Yes\n"; return 0; } } } std::cout << "No\n"; }