#960791 (C++23) No.2674 k-Walk on Bipartite

提出ソース

結果

問題	No.2674 k-Walk on Bipartite
ユーザー	れび
提出日時	2024-03-15 22:59:19
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	8,611 bytes
コンパイル時間	5,217 ms
コンパイル使用メモリ	331,320 KB
実行使用メモリ	15,744 KB
最終ジャッジ日時	2024-09-30 02:34:07
合計ジャッジ時間	8,266 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	86 ms 13,056 KB
testcase_08	AC	107 ms 11,800 KB
testcase_09	AC	73 ms 12,800 KB
testcase_10	AC	132 ms 13,696 KB
testcase_11	AC	82 ms 11,136 KB
testcase_12	AC	136 ms 12,800 KB
testcase_13	AC	68 ms 11,732 KB
testcase_14	AC	18 ms 8,832 KB
testcase_15	AC	142 ms 14,676 KB
testcase_16	AC	98 ms 13,696 KB
testcase_17	AC	103 ms 11,520 KB
testcase_18	AC	41 ms 9,344 KB
testcase_19	AC	86 ms 12,416 KB
testcase_20	AC	78 ms 12,628 KB
testcase_21	AC	113 ms 12,340 KB
testcase_22	AC	148 ms 15,744 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	1 ms 5,248 KB
testcase_34	AC	1 ms 5,248 KB
testcase_35	AC	1 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	1 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i,t,n) for(long long i=t;i<n;i++)
#define rep2(i,A) for(auto &i:A)
#define Sort(a) sort(a.begin(),a.end())
#define rSort(a,n,m) sort(a.begin()+n,a.begin()+m+1)
#define Reverse(a) reverse(a.begin(),a.end())
#define rReverse(a,n,m) reverse(a.begin()+n,a.begin()+m+1)
#define MOD1 998244353
#define MOD2 1000000007
#define sign(i) -1*pow(-1,i)
#define vi(A,N,i)  vector<long long> A(N,i)
#define vd(A,N,i)  vector<double> A(N,i)
#define vc(A,N,i)  vector<char> A(N,i)
#define vs(A,N,i)  vector<string> A(N,i)
#define vb(A,N,i)  vector<bool> A(N,i)
#define vp(A,N,i)  vector<Pair> A(N,{i,i})
#define vvi(A,N,M,i) vector<vector<long long>> A(N,vector<long long>(M,i))
#define vvd(A,N,M,i) vector<vector<double>> A(N,vector<double>(M,i))
#define vvc(A,N,M,i) vector<vector<char>> A(N,vector<char>(M,i))
#define vvb(A,N,M,i) vector<vector<bool>> A(N,vector<bool>(M,i))
#define vvvi(A,N,M,L,i) vector<vector<vector<ll>>> A(N,vector<vector<ll>>(M,vector<ll>(L,i)))
#define ll long long
#define INF ((1LL<<62)-(1LL<<31))
#define ALL(a) (a).begin(),(a).end()
//((a+b+c)-max(a,max(b,c))-min(a,min(b,c)))

//cout << fixed << setprecision(桁数);
using VVi=vector<vector<ll>>;
using Pair=pair<ll,ll>;
using graphi=vector<vector<ll>>;
using graphp=vector<vector<Pair>>;
struct Plane{
  ll x;
  ll y;
};
struct Path{
  ll cost;
  ll to;
};
template<typename T>
void CIN(vector<T> &A){
  rep(i,0,(ll)A.size()){
    cin>>A[i];
  }
  return;
}
struct ThreePlane{
  ll x,y,z;
  ThreePlane(ll X=0,ll Y=0,ll Z=0):x(X),y(Y),z(Z){}
  bool operator<(const ThreePlane& other) const {
    return x<other.x;
  }
  bool operator<=(const ThreePlane& other) const {
    return x<=other.x;
  }
  bool operator>(const ThreePlane& other) const {
    return x>other.x;
  }
  bool operator>=(const ThreePlane& other) const {
    return x>=other.x;
  }
};
struct FourPlane{
  ll dist;
  ll x;
  ll y;
  ll stat;
};
struct Fraction{
    ll p,q,r;
    Fraction(ll P = 0, ll Q = 1,ll R = 1): p(P), q(Q),r(R){}
    bool operator<(const Fraction &other)const{
      if(p*other.q != other.p*q){
        return p*other.q < other.p*q;
      }else{
        return r>other.r;
      }
        
    }
};
struct Matrix{//正方のみ
  vector<vector<ll>> mat;
  Matrix(ll size):mat(vector<vector<ll>>(size,vector<ll>(size,0))){}
  void showerr(){
    rep2(i,mat){
      rep2(j,i)cerr<<j<<" ";
      cerr<<endl;
    }
    return;
  }
  void showout(){
    rep2(i,mat){
      rep2(j,i)cout<<j<<" ";
      cout<<endl;
    }
    return;
  }
};
template<typename T>
struct Zaatu{
  bool sorted;
  vector<T> za;
  Zaatu():sorted(false){}
  void add(T x){
    za.push_back(x);
    sorted=false;
  }
  void build(){
    sort(std::begin(za),std::end(za));
    sorted=true;
    za.erase(unique(std::begin(za),std::end(za)),std::end(za));
  }
  ll size(){
    if(!sorted)build();
    return (ll)za.size();
  }
  const T &operator[](int i){
    if(!sorted)build();
    return za[i];
  }
  ll get(const T &x){//x以上の最小値のindex
    if(!sorted)build();
    return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);
  }
  vector<ll> get(vector<T> mo){
    if(!sorted)build();
    vector<ll> result;
     transform(std::begin(mo),std::end(mo),back_inserter(result),[&](const T &x){
      return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);
    });
    return result;
  }
  typename vector<T>::iterator begin(){
    if(!sorted)build();
    return std::begin(za);
  }
  typename vector<T>::iterator end(){
    if(!sorted)build();
    return std::end(za);
  }
};

ll POW(ll a,ll b,ll mod){
  ll c=1;
  a%=mod;
  while(b!=0){
    if(b%2){
      c*=a;
      c%=mod;
    }
    a*=a;
    a%=mod;
    b/=2;
  }
  return c;
}
ll GCD(ll a,ll b){
  if(b==0)return a;
  return GCD(b,a%b);
}
pair<long long, long long> extGCD(long long a, long long b) {// ax+by=1 solver
  if (b == 0) return make_pair(1, 0);
  long long x,y;
  tie(y,x)=extGCD(b,a%b);
  y-=a/b*x;
  return make_pair(x,y);
}
ll SQRT(ll a){
  ll low,high,mid;
  low=0;
  high=1LL<<31;
  while(high-low!=1){
    mid=(low+high)/2;
    if(mid*mid<=a){
      low=mid;
    }else{
      high=mid;
    }
  }
  return low;
}
string strmin(string x,string y){
  ll minlength=min((int)x.size(),(int)y.size());
  rep(i,0,minlength){
    if(x[i]>y[i])return y;
    if(x[i]<y[i])return x;
  }
  if((int)x.size()>(int)y.size())return y;
  return x;
}
ll LCS(string x,string y){
  ll xsize=(ll)x.size();
  ll ysize=(ll)y.size();
  vvi(dp,xsize+1,ysize+1,0);
  rep(i,1,xsize+1){
    rep(j,1,ysize+1){
      if(x[i-1]==y[j-1])dp[i][j]=max(max(dp[i-1][j-1]+1,dp[i][j-1]),dp[i-1][j]);
      else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
    }
  }
  return dp[xsize][ysize];
}
ll Factorial(ll n,ll mod){
  ll a=1;
  if(n>=mod)return 0;
  rep(i,1,n+1){
    a*=i;
    a%=mod;
  }
  return a;
}
ll Combination(ll n,ll k,ll mod){
  if(n<k)return 0;
  ll a=Factorial(n,mod);
  ll b=inv_mod(Factorial(k,mod),mod);
  ll c=inv_mod(Factorial(n-k,mod),mod);
  a*=b;
  a%=mod;
  a*=c;
  a%=mod;
  return a;
}
vector<pair<char,long long>> RLE(string x,char s=' ',long long a=0,vector<pair<char,long long>> res={}){
  for(auto i:x){
    if(s==i){
      a++;
    }else{
      if(s!=' ')res.push_back({s,a});
      s=i,a=1;
    }
  }
  res.push_back({s,a});
  return res;
}
vector<ll> cu1d(vector<ll> A){
  ll cu1=A.size();
  vector<ll> res(cu1+1,0);
  rep(i,0,cu1)res[i+1]=A[i];
  rep(i,1,cu1+1)res[i]+=res[i-1];
  return res;
}
vector<vector<ll>> cu2d(vector<vector<ll>> A){
  ll cu1=A.size(),cu2=A[0].size();
  vector<vector<ll>> res(cu1+1,vector<ll>(cu2+1,0));
  rep(i,0,cu1)rep(j,0,cu2)res[i+1][j+1]=A[i][j];
  rep(i,1,cu1+1)rep(j,0,cu2+1)res[i][j]+=res[i-1][j];
  rep(j,0,cu1+1)rep(i,1,cu2+1)res[j][i]+=res[j][i-1];
  return res;
}
ll LIS(vector<ll> A){
  ll a=(ll)A.size();
  vector<ll> result(a,INF);
  ll answer=0;
  rep(i,0,a){
    ll ok=-1;
    ll ng=a;
    while(ng-ok!=1){
      ll mid=(ok+ng)/2;
      if(A[i]<=result[mid])ng=mid;
      else ok=mid;
    }
    result[ok+1]=A[i];
    answer=max(answer,ok+2);
  }
  return answer;
}
vector<ll> zaatu(vector<ll> A){
  vector<ll> B=A;
  Sort(B);
  B.erase(unique(ALL(B)),end(B));
  vector<ll> res;
   transform(ALL(A),back_inserter(res),[&](const ll &x){
    return lower_bound(ALL(B),x)-begin(B);
  });
  return res;
}
vector<string> trim(vector<string> A){
  bool frag=0;
  char s='#';
  ll h=(ll)A.size();
  ll w=(ll)A[0].size();
  ll a=-1,b=h,c=-1,d=w;
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;
    if(frag)break;
    a=i;
  }
  frag=0;
  for(ll i=h-1;i>=0;i--){
    for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;
    if(frag)break;
    b=i;
  }
  frag=0;
  for(ll i=0;i<w;i++){
    for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;
    if(frag)break;
    c=i;
  }
  frag=0;
  for(ll i=w-1;i>=0;i--){
    for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;
    if(frag)break;
    d=i;
  }
  vector<string> B(b-a-1,"");
  for(ll i=a+1;i<b;i++)for(ll j=c+1;j<d;j++)B[i-a-1]+=A[i][j];
  return B;
}
char to_upper(char s){
  if('a'<=s){
    s-=32;
  }
  return s;
}
char to_lower(char s){
  if(s<='Z'){
    s+=32;
  }
  return s;
}
vector<vector<ll>> Warshall(vector<vector<ll>> A){
  ll a=A.size();
  rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
  return A;
}


//Warshall rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);
long long a,b,c,d,e,f,g,h,ans=0;
string w,x="",y="",z="";
char s,t,u;
bool frag=false,frag1=false,frag2=false;
vector<ll> X={1,0,-1,0},Y={0,1,0,-1};
bool dp[5050][8192][4]={};
// vvvi(dp,5050,8192,2,0);
int main(){
	cin>>a>>b>>c>>d>>e;
	c--,d--;
	graphi A(a);
	rep(i,0,b){
		cin>>f>>g;
		f--,g--;
		A[f].push_back(g);
		A[g].push_back(f);
	}
	vi(B,a,INF);
	B[c]=0;
	queue<ll> Q;
	Q.push(c);
	while(!Q.empty()){
		ll q=Q.front();
		Q.pop();
		rep2(i,A[q]){
			if(B[i]!=INF)continue;
			B[i]=B[q]+1;
			Q.push(i);
		}
	}
	ll k=e;
	if(B[d]==INF){
		rep(i,0,a){
			if(i==d)continue;
			if(B[i]==INF){
				cout<<"Unknown"<<endl;
		        return 0;
			}
			if(B[i]%2!=e%2){
				cout<<"Unknown"<<endl;
		        return 0;
			}
		}
		cout<<"No"<<endl;
		return 0;
	}else{
		ll p=0,q=0;
		rep(i,0,a){
			if(B[i]!=INF){
				if(B[i]%2)p++;
				else q++;
			}
		}
		if(p+q==a){
			if(b==p*q){
				if(e%2!=B[d]%2){
				cout<<"No"<<endl;
				return 0;
			}
			if(k>=B[d]){
				cout<<"Yes"<<endl;
				return 0;
			}
			cout<<"No"<<endl;
			return 0;
			}
		}
		if(e%2!=B[d]%2){
			cout<<"No"<<endl;
			return 0;
		}
		if(k>=B[d]){
			cout<<"Yes"<<endl;
			return 0;
		}
		cout<<"Unknown"<<endl;
		return 0;
	}
	
}

yukicoder

結果

テストケース

ソースコード