結果

問題 No.3291 K-step Navigation
コンテスト
ユーザー 蜜蜂
提出日時 2025-10-03 23:00:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,834 bytes
コンパイル時間 3,254 ms
コンパイル使用メモリ 293,772 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-03 23:00:13
合計ジャッジ時間 5,344 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 41 WA * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In lambda function:
main.cpp:78:17: warning: overflow in conversion from ‘double’ to ‘std::vector<int>::value_type’ {aka ‘int’} changes value from ‘2.0e+18’ to ‘2147483647’ [-Woverflow]
   78 |     vi dist(2*n,2e18);
      |                 ^~~~

ソースコード

diff # 

// g++-15 1.cpp -std=c++20 -O2 -I .
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;

#include <atcoder/modint>
using namespace atcoder;

using ll = long long;
using ld = long double;
 
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=(start);i<(ll)(end);i++)
#define per(i,start,end) for(ll i=(start);i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

random_device seed;
mt19937_64 randint(seed());

ll grr(ll mi, ll ma) { // [mi, ma)
    return mi + randint() % (ma - mi);
}

int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n,m,s,t;
  ll k;
  cin>>n>>m>>k>>s>>t;
  s--;t--;

  if(s>t)swap(s,t);

  vvi g(n);
  vi deg(n,0);
  int nei=0;
  rep(i,0,m){
    int u,v;cin>>u>>v;
    u--;v--;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
    deg[u]++;deg[v]++;
    if(u==s&&v==t)nei=1;
  }

  if(!nei){
    if(deg[s]==0&&deg[t]==0&&k%2==0){
      cout<<"No\n";
    }
    else cout<<"Yes\n";
    return 0;
  }

  auto is_ok=[&](){
    vi dist(2*n,2e18);
    dist[2*s]=0;
    using P = pair<ll,int>;
    pq_small(P) que;
    que.push({0,2*s});
    while(!que.empty()){
      auto [dst,pos]=que.top();
      que.pop();
      if(dist[pos]<dst)continue;
      pos=pos/2;
      for(int nxt:g[pos]){
        int pos2=2*nxt+(dst+1)%2;
        if(dist[pos2]>dst+1){
          dist[pos2]=dst+1;
          que.push({dst+1,pos2});
        }
      }
    }
    ll cst=dist[2*t+k%2];
    if(cst<=k)return 1;
    else return 0;
  };

  if(deg[s]>1||deg[t]>1){
    cout<<"Yes\n";
    return 0;
  }
  else{
    vi seen(n,0);
    for(int nxt:g[s])seen[nxt]=1;
    rep(i,0,n){
      if(seen[i]){
        seen[i]=0;
        continue;
      }
      g[s].emplace_back(i);
      g[i].emplace_back(s);
      int b=is_ok();
      if(b){
        cout<<"Yes\n";
        return 0;
      }
      g[s].pop_back();
      g[i].pop_back();
    }
    for(int nxt:g[t])seen[nxt]=1;
    rep(i,0,n){
      if(seen[i]){
        seen[i]=0;
        continue;
      }
      g[t].emplace_back(i);
      g[i].emplace_back(t);
      int b=is_ok();
      if(b){
        cout<<"Yes\n";
        return 0;
      }
      g[t].pop_back();
      g[i].pop_back();
    }
  }

  cout<<"No\n";
}
0