結果

問題 No.3291 K-step Navigation
ユーザー t98slider
提出日時 2025-10-03 23:02:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,644 bytes
コンパイル時間 2,105 ms
コンパイル使用メモリ 211,304 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-03 23:02:11
合計ジャッジ時間 4,494 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26 WA * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class T> struct csr {
    using itr = typename std::vector<T>::iterator;
    struct Node {
        itr st, en;
        itr begin() { return st; }
        itr end() { return en; }
        int size() { return en - st; }
        T operator[](int p){ return st[p]; }
    };
    const int N;
    std::vector<int> start;
    std::vector<T> E;
    std::vector<std::pair<int,T>> edge;
    csr(int n) : N(n), start(n + 1) {}
    void add_edge(int u, T v){
        assert(0 <= u && u < N);
        start[u + 1]++;
        edge.emplace_back(u, v);
    }
    void build(){
        E.resize(edge.size());
        for(int i = 0; i < N; i++) start[i + 1] += start[i];
        auto cnt = start;
        for(auto [u, v] : edge) E[cnt[u]++] = v;
    }
    Node operator[](int p) {
        return Node{E.begin() + start[p], E.begin() + start[p + 1]};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, s, t, u, v;
    ll k;
    cin >> n >> m >> k >> s >> t;
    s--, t--;
    if(k % 2 == 1){
        cout << "Yes\n";
        return 0;
    }
    assert(s != t);
    csr<int> g(n);
    vector<array<bool,2000>> B(n);
    for(int i = 0; i < n; i++){
        B[i].fill(false);
        B[i][i] = true;
    }
    for(int i = 0; i < m; i++){
        cin >> u >> v;
        u--, v--;
        B[u][v] = B[v][u] = true;
        g.add_edge(u, v);
        g.add_edge(v, u);
    }
    g.build();
    deque<pair<int,int>> que;
    auto bfs = [&](int from){
        vector<array<ll,2>> dp(n);
        for(int i = 0; i < n; i++) dp[i].fill(1ll << 62);
        que.emplace_back(from, 0);
        dp[from][0] = 0;
        while(!que.empty()){
            auto [v, s] = que.front();
            que.pop_front();
            for(int u = 0; u < n; u++){
                if(B[v][u]){
                    if(dp[v][s] + 1 >= dp[u][s ^ 1]) continue;
                    dp[u][s ^ 1] = dp[v][s] + 1;
                    que.emplace_front(u, s ^ 1);
                }else{
                    if(dp[v][s] + (1ll << 60) + 1 >= dp[u][s ^ 1]) continue;
                    dp[u][s ^ 1] = dp[v][s] + (1ll << 60) + 1;
                    que.emplace_back(u, s ^ 1);
                }
            }
        }
        return dp;
    };
    auto d1 = bfs(s);
    auto v1 = d1[t][0];
    if(v1 < (1ll << 61)) v1  -= 1ll << 60;
    if(v1 <= k && (k - v1) % 2 == 0){
        cout << "Yes\n";
        return 0;
    }
    v1 = d1[t][1];
    if(v1 < (1ll << 61)) v1  -= 1ll << 60;
    if(v1 <= k && (k - v1) % 2 == 0){
        cout << "Yes\n";
        return 0;
    }
    cout << "No\n";
}
0