結果
問題 | No.2674 k-Walk on Bipartite |
ユーザー |
|
提出日時 | 2024-03-15 22:59:19 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 132 ms / 2,000 ms |
コード長 | 1,904 bytes |
コンパイル時間 | 11,689 ms |
コンパイル使用メモリ | 283,988 KB |
最終ジャッジ日時 | 2025-02-20 05:52:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#pragma GCC optimize("O3")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")#pragma GCC target("avx,avx2")#include <bits/stdc++.h>#define INF 1000000001LL#define LNF 1000000000000000001LL#define MOD 1000000007LL#define MAX 200001#define long long long#define all(x) x.begin(),x.end()using namespace std;vector<int> graph[MAX];int main(){ios_base::sync_with_stdio(0);cin.tie(0);int n,m;cin >> n >> m;int s,e,k;cin >> s >> e >> k;for(int i = 0; i<m; i++){int a,b;cin >> a >> b;graph[a].push_back(b);graph[b].push_back(a);}vector<int> vis(n+1,-1);queue<int> q;q.push(s);while(!q.empty()){int x = q.front();q.pop();for(int y : graph[x]){if(vis[y] == -1){if(vis[x] == -1)vis[y] = 1;elsevis[y] = vis[x]+1;q.push(y);}}}if(n == 1){cout << "No\n";return 0;}if(vis[e] <= k){if(vis[e] == -1){if(s == e){if(k%2 == 0){cout << "Unknown\n";}elsecout << "No\n";return 0;}if(n == 2 && k%2){cout << "Unknown\n";}else if(n == 2){cout << "No\n";}elsecout << "Unknown\n";}else if(vis[e]%2 == k%2)cout << "Yes\n";elsecout << "No\n";}else{if(vis[e]%2 == k%2)cout << "Unknown\n";elsecout << "No\n";}return 0;}