結果

問題 No.2674 k-Walk on Bipartite
ユーザー ococonomy1
提出日時 2024-03-15 21:38:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 5,747 bytes
コンパイル時間 1,348 ms
コンパイル使用メモリ 120,392 KB
最終ジャッジ日時 2025-02-20 04:45:06
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <climits>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
#define TEST cerr << "TEST" << endl
#define AMARI 998244353
//#define AMARI 1000000007
#define el '\n'
#define El '\n'
class ococo_unionfind {
//
//
//
//
//
//
//
public:
ococo_unionfind(int n = 0) {
for(int i = 0; i < n; i++) vinsert();
}
int simakosuu = 0;
// g[i] = {,rank}
// rank:
vector<pair<int, int>> g;
// rs[i] =
//
vector<int> rs;
// O(1)
void vinsert(void) {
g.emplace_back(g.size(), 1);
simakosuu++;
rs.push_back(1);
}
// O(α(N))
int ne(int a) {
if(g[a].first == a) return a;
else {
return g[a].first = ne(g[a].first);
}
}
// O(logN)
void einsert(int a, int b) {
if(a != b) {
int a1 = ne(a), a2 = ne(b);
if(a1 != a2) {
simakosuu--;
int rs12sum = rs[a1] + rs[a2];
rs[a1] = rs12sum;
rs[a2] = rs12sum;
if(g[a1].second < g[a2].second) {
g[a1].first = a2;
g[a2].second = max(g[a1].second + 1, g[a2].second);
} else {
g[a2].first = a1;
g[a1].second = max(g[a2].second + 1, g[a1].second);
}
}
}
}
void peinsert(pair<int,int> p){
einsert(p.first,p.second);
return;
}
// 2 O(α(N))
bool renketucheck(int a, int b) {
if(ne(a) == ne(b)) return true;
else return false;
}
bool prenketucheck(pair<int,int> p){
return renketucheck(p.first,p.second);
}
// O(1)
int islandnum(void) {
return simakosuu;
}
//
// O(α(N))
int islandsize(int a) {
return rs[ne(a)];
}
};
#define MULTI_TEST_CASE false
void solve(void){
//
//
//
//
//
//F(E)
//Es,t k
//E,F
int n,m;
int s,t,k;
cin >> n >> m >> s >> t >> k;
s--; t--;
vector<vector<int>> g(n);
ococo_unionfind uf(n);
while(m--){
int u,v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
uf.einsert(u,v);
}
if(n == 1){
cout << "No" << El;
return;
}
if(n == 2){
// Yes
if(((s == t) == (k % 2 == 0)) && uf.islandnum() == 1){
cout << "Yes" << el;
return;
}
if((s == t) == (k % 2 == 0)){
cout << "Unknown" << el;
return;
}
cout << "No" << el;
return;
}
if(s == t){
if(k % 2 == 0 && uf.islandsize(s) != 1)cout << "Yes" << el;
if(k % 2 == 0 && uf.islandsize(s) == 1)cout << "Unknown" << el;
if(k % 2 == 1) cout << "No" << el;
return;
}
if(!uf.renketucheck(s,t)){
cout << "Unknown" << el;
return;
}
vector<int> dist(n,-1);
dist[s] = 0;
queue<int> que; que.push(s);
while(!que.empty()){
int fr = que.front();
que.pop();
for(int i = 0; i < g[fr].size(); i++){
int to = g[fr][i];
if(dist[to] != -1)continue;
dist[to] = dist[fr] + 1;
que.push(to);
}
}
if(dist[t] % 2 != k % 2){
cout << "No" << el;
return;
}
if(dist[t] <= k){
cout << "Yes" << el;
return;
}
cout << "Unknown" << el;
return;
}
void calc(void){
return;
}
signed main(void){
cin.tie(nullptr);
ios::sync_with_stdio(false);
calc();
int t = 1;
if(MULTI_TEST_CASE)cin >> t;
while(t--){
solve();
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0