結果
| 問題 |
No.2674 k-Walk on Bipartite
|
| コンテスト | |
| ユーザー |
 nouka28
|
| 提出日時 | 2024-03-15 22:29:47 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 177 ms / 2,000 ms |
| コード長 | 10,370 bytes |
| コンパイル時間 | 5,704 ms |
| コンパイル使用メモリ | 323,596 KB |
| 実行使用メモリ | 20,012 KB |
| 最終ジャッジ日時 | 2024-09-30 01:54:53 |
| 合計ジャッジ時間 | 7,958 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 36 |
ソースコード
#pragma region template
#include<bits/stdc++.h>
using namespace std;
//other
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#include<atcoder/all>
using namespace atcoder;
// #include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
using zint = atcoder::modint1000000007;
// using mint=modint;
#define int long long
#define pb push_back
#define eb emplace_back
#define ep emplace
#define len(a) (int)a.size()
#define BIT(a,b) ((a)>>(b)&1)
// #define endl "\n"
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//using
using ll=long long;
using i32=signed;
using i64=long long;
using i128=__int128_t;
using ld=long double;
using ull=unsigned long long;
using uint=unsigned;
using pcc=pair<char,char>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using pdd=pair<ld,ld>;
using vi=vector<int>;
using vl=vector<ll>;
using vvi=vector<vi>;
using vvl=vector<vl>;
using vvvi=vector<vvi>;
using vvvl=vector<vvl>;
template<class T>using V=vector<T>;
template<class T>using VV=vector<V<T>>;
template<class T>using VVV=vector<VV<T>>;
template<class T>using VVVV=vector<VVV<T>>;
template<class T>using VVVVV=vector<VVVV<T>>;
template<class T>using pqmin=priority_queue<T,vector<T>,greater<T>>;
template<class T>using pqmax=priority_queue<T>;
// template<class T>using pbds=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define chmax(a,b) (a)=max((a),(b))
#define chmin(a,b) (a)=min((a),(b))
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=998244353;
const int MOD2=1000000007;
const ld PI=3.1415926535897932384626433832795028841971;
const ld DINF=numeric_limits<ld>::infinity();
const ld EPS=1e-9;
const ll di[]={0,1,0,-1,1,-1,1,-1};
const ll dj[]={1,0,-1,0,1,1,-1,-1};
template<class T>
constexpr auto min(T a,T b,T c){
return min(a,min(b,c));
}
template<class... T>
constexpr auto min(T... a){
return min(initializer_list<common_type_t<T...>>{a...});
}
template<class T>
constexpr auto max(T a,T b,T c){
return max(a,max(b,c));
}
template<class... T>
constexpr auto max(T... a){
return max(initializer_list<common_type_t<T...>>{a...});
}
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n)for(ll i=n;i--;)
#define rrep2(i,n)for(ll i=n;i--;)
#define rrep3(i,a,b)for(ll i=b;i-->(a);)
#define rrep4(i,a,b,c)for(ll=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrpe4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define isum(...) accumulate(all(__VA_ARGS__),0LL)
#define dsum(...) accumulate(all(__VA_ARGS__),0.0L)
#define Msum(...) accumulate(all(__VA_ARGS__),0_M)
#define elif else if
#define INT(...) int __VA_ARGS__;input(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;input(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;input(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;input(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;input(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;input(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;input(__VA_ARGS__)
//io
//in
void scan(){}
void scan(signed &a){cin>>a;}
void scan(unsigned &a){cin>>a;}
void scan(long& a){cin>>a;}
void scan(long long& a){cin>>a;}
void scan(unsigned long long&a){cin>>a;}
void scan(char& a){cin>>a;}
void scan(float& a){cin>>a;}
void scan(double& a){cin>>a;}
void scan(long double& a){cin>>a;}
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){cin>>a;}
template<class T> void scan(vector<T>&);
template<class T, int size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, int size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); }
template<class T, int size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, int size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void input(){}
template<class Head,class...Tail> void input(Head& head,Tail&... tail){scan(head);input(tail...);}
//out
void puts(){ putchar(' '); }
void puts(bool a){ printf("%d", a); }
void puts(signed a){ printf("%d", a); }
void puts(unsigned a){ printf("%u", a); }
void puts(long a){ printf("%ld", a); }
void puts(long long a){ printf("%lld", a); }
void puts(unsigned long long a){ printf("%llu", a); }
void puts(char a){ printf("%c", a); }
void puts(char a[]){ printf("%s", a); }
// void puts(const char a[]){ printf("%s", a); }
void puts(float a){ printf("%.15f", a); }
void puts(double a){ printf("%.15f", a); }
void puts(long double a){ printf("%.15Lf", a); }
void puts(const string& a){ for(auto&& i : a) puts(i); }
template<class T> void puts(const complex<T>& a){ if(a.real() >= 0) puts('+'); puts(a.real()); if(a.imag() >= 0) puts('+'); puts(a.imag()); puts('i'); }
template<class T> void puts(const vector<T>&);
template<class T, int size> void puts(const array<T, size>&);
template<class T, class L> void puts(const pair<T, L>& p);
template<class T, int size> void puts(const T (&)[size]);
template<class T> void puts(const vector<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const deque<T>& a){ if(a.empty()) return; puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const set<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const multiset<T>& a){ if(a.empty()) return; puts(*a.begin()); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T, int size> void puts(const array<T, size>& a){ puts(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); puts(*i); } }
template<class T, class L> void puts(const pair<T, L>& p){ putchar('(');puts(p.first); putchar(' '); puts(p.second); putchar(')');}
template<class T, int size> void puts(const T (&a)[size]){ puts(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); puts(*i); } }
template<class T> void puts(const T& a){ cout << a; }
int print(){ putchar('\n'); return 0; }
template<class T> int print(const T& t){ puts(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int print(const Head& head, const Tail&... tail){ puts(head); putchar(' '); print(tail...); return 0; }
#pragma endregion
#pragma region commonly used
int digitsum(string s){
int res=0;
rep(i,(int)s.size()){
res+=s[i]-'0';
}
return res;
}
//乱数系
random_device rnd;
mt19937 mt(rnd());
const long long MT_MAX=LINF;
uniform_int_distribution<long long> rd(0,MT_MAX);
double randd(){
return 1.0*rd(mt)/MT_MAX;
}
long long randint(long long a,long long b){
// [a,b]の乱数を生成
return a+rd(mt)%(b-a+1);
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
__int128 parse(string &s) {
__int128 ret = 0;
for (int i = 0; i < (int)s.length(); i++)
if ('0' <= s[i] && s[i] <= '9')
ret = 10 * ret + s[i] - '0';
return ret;
}
// #include<boost/multiprecision/cpp_int.hpp>
// using lint=boost::multiprecision::cpp_int;
#pragma endregion
vector<int> dijkstra(vector<vector<pair<int,int>>> &g,int start){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
vector<bool> kakutei(g.size(),false);
vector<int> dis(g.size(),(int)1e15);
q.push(make_pair(0,start));
dis[start]=0;
while(!q.empty()){
pair<int,int> p=q.top();q.pop();
int pos=p.second,cost=p.first;
if(kakutei[pos])continue;
kakutei[pos]=true;
for(auto nex:g[pos]){
int npos=nex.first,ncos=nex.second;
if(dis[npos]>cost+ncos){
dis[npos]=cost+ncos;
q.push(make_pair(dis[npos],npos));
}
}
}
return dis;
}
signed main(){
INT(n,m);
INT(s,t,k);s--;t--;
VV<pair<int,int>> g(n);
dsu ds(n);
rep(i,m){
INT(a,b);a--;b--;
g[a].pb({b,1});
g[b].pb({a,1});
ds.merge(a,b);
}
auto d=dijkstra(g,s);
// print(d);
if(n==1){
cout<<"No"<<endl;
return 0;
}
if(n==2){
if(s==t){
if(k%2){
cout<<"No"<<endl;
return 0;
}else{
if(ds.size(s)>1){
cout<<"Yes"<<endl;
return 0;
}else{
cout<<"Unknown"<<endl;
return 0;
}
}
}else{
if(k%2==0){
cout<<"No"<<endl;
return 0;
}else{
if(ds.size(s)>1){
cout<<"Yes"<<endl;
return 0;
}else{
cout<<"Unknown"<<endl;
return 0;
}
}
}
}
if(!ds.same(s,t)){
cout<<"Unknown"<<endl;
return 0;
}
if((d[t]%2)!=(k%2)){
cout<<"No"<<endl;
return 0;
}
assert((d[t]%2)==(k%2));
if(d[t]<=k&&ds.size(t)>1){
cout<<"Yes"<<endl;
return 0;
}
cout<<"Unknown"<<endl;
}