結果
問題 | No.2674 k-Walk on Bipartite |
ユーザー |
![]() |
提出日時 | 2024-03-15 21:59:33 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 2,102 bytes |
コンパイル時間 | 5,558 ms |
コンパイル使用メモリ | 315,148 KB |
実行使用メモリ | 15,220 KB |
最終ジャッジ日時 | 2024-09-30 01:08:18 |
合計ジャッジ時間 | 7,936 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using ll = long long; using ull = unsigned long long; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define REP(i, m, n) for(int i = (int)(m); i < (int)(n); i++) using namespace std; using namespace atcoder; using mint = modint998244353; const int inf = 1000000007; const ll longinf = 1ll << 60; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; dsu uf(n * 2); int s, t, k; cin >> s >> t >> k; --s; --t; vector<vector<int>> g(n); rep(i, m) { int x, y; cin >> x >> y; --x; --y; uf.merge(x, y + n); uf.merge(x + n, y); g[x].push_back(y); g[y].push_back(x); } vector<int> dist(n, inf); dist[s] = 0; queue<int> q; q.push(s); while(q.size()) { int x = q.front(); q.pop(); for(auto to : g[x]) { if(dist[to] == inf) { dist[to] = dist[x] + 1; q.push(to); } } } if(uf.same(s, t)) { if(k % 2 == 1) { cout << "No" << endl; } else if(s == t) { if(g[s].size() > 0) { cout << "Yes" << endl; } else if(n == 1) { cout << "No" << endl; } else { cout << "Unknown" << endl; } } else if(dist[t] <= k) { cout << "Yes" << endl; } else { cout << "Unknown" << endl; } } else if(uf.same(s, t + n)) { if(k % 2 == 0) { cout << "No" << endl; } else if(dist[t] <= k) { cout << "Yes" << endl; } else { cout << "Unknown" << endl; } } else { if(n == 1) { cout << "No" << endl; } else if(n == 2) { if(k % 2 == 1) { cout << "Unknown" << endl; } else { cout << "No" << endl; } } else { cout << "Unknown" << endl; } } return 0; }