結果
問題 | 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; else vis[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"; } else cout << "No\n"; return 0; } if(n == 2 && k%2) { cout << "Unknown\n"; } else if(n == 2) { cout << "No\n"; } else cout << "Unknown\n"; } else if(vis[e]%2 == k%2) cout << "Yes\n"; else cout << "No\n"; } else { if(vis[e]%2 == k%2) cout << "Unknown\n"; else cout << "No\n"; } return 0; }