結果
| 問題 |
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);
| ^~~~
ソースコード
// 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&°[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";
}
蜜蜂