結果

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

ソースコード

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();
    queue<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 << 60);
        que.emplace(from, 0);
        dp[from][0] = 0;
        while(!que.empty()){
            auto [v, s] = que.front();
            que.pop();
            for(auto u : g[v]){
                if(dp[v][s] + 1 >= dp[u][s ^ 1]) continue;
                dp[u][s ^ 1] = dp[v][s] + 1;
                que.emplace(u, s ^ 1);
            }
        }
        return dp;
    };
    auto d1 = bfs(s);
    auto d2 = bfs(t);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(B[i][j]) continue;
            for(int S = 0; S < 4; S++){
                ll c = d1[i][S / 2] + d2[j][S & 1] + 1;
                if(c <= k && (k - c) % 2 == 0){
                    cout << "Yes\n";
                    return 0;
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            ll c = d1[i][j / 2] + d2[i][j & 1];
            if(c <= k && (k - c) % 2 == 0){
                cout << "Yes\n";
                return 0;
            }
        }
    }
    for(int v = 0; v < n; v++){
        if(B[s][v])continue;
        d1[v][1] = 1;
        que.emplace(v, 1);
    }
    while(!que.empty()){
        auto [v, s] = que.front();
        que.pop();
        for(auto u : g[v]){
            if(d1[v][s] + 1 >= d1[u][s ^ 1]) continue;
            d1[u][s ^ 1] = d1[v][s] + 1;
            que.emplace(u, s ^ 1);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            ll c = d1[i][j / 2] + d2[i][j & 1];
            if(c <= k && (k - c) % 2 == 0){
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
}
0