結果

問題 No.2674 k-Walk on Bipartite
ユーザー Aeren
提出日時 2024-03-15 22:46:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 274 ms / 2,000 ms
コード長 8,757 bytes
コンパイル時間 3,693 ms
コンパイル使用メモリ 269,704 KB
実行使用メモリ 45,236 KB
最終ジャッジ日時 2024-09-30 02:15:00
合計ジャッジ時間 7,455 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
template<bool Enable_small_to_large = true>
struct disjoint_set{
    int n, _group_count;
    vector<int> p;
    vector<list<int>> group;
    disjoint_set(){ }
    disjoint_set(int n): n(n), _group_count(n), p(n, -1), group(n){ assert(n >= 0);
        for(auto i = 0; i < n; ++ i) group[i] = {i};
    }
    int make_set(){
        p.push_back(-1);
        group.push_back(list<int>{p});
        ++ _group_count;
        return n ++;
    }
    int root(int u){
        return p[u] < 0 ? u : p[u] = root(p[u]);
    }
    bool share(int a, int b){
        return root(a) == root(b);
    }
    int size(int u){
        return -p[root(u)];
    }
    bool merge(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _group_count;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
        p[u] += p[v], p[v] = u;
        group[u].splice(group[u].end(), group[v]);
        return true;
    }
    bool merge(int u, int v, auto act){
        u = root(u), v = root(v);
        if(u == v) return false;
        -- _group_count;
        bool swapped = false;
        if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
        p[u] += p[v], p[v] = u;
        group[u].splice(group[u].end(), group[v]);
        act(u, v, swapped);
        return true;
    }
    int group_count() const{
        return _group_count;
    }
    const list<int> &group_of(int u){
        return group[root(u)];
    }
    vector<vector<int>> group_up(){
        vector<vector<int>> g(n);
        for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
        g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
        return g;
    }
    void clear(){
        _group_count = n;
        fill(p.begin(), p.end(), -1);
        for(auto i = 0; i < n; ++ i) group[i] = {i};
    }
    friend ostream &operator<<(ostream &out, disjoint_set dsu){
        auto gs = dsu.group_up();
        out << "{";
        if(!gs.empty()) for(auto i = 0; i < (int)gs.size(); ++ i){
            out << "{";
            for(auto j = 0; j < (int)gs[i].size(); ++ j){
                out << gs[i][j];
                if(j + 1 < (int)gs[i].size()) out << ", ";
            }
            out << "}";
            if(i + 1 < (int)gs.size()) out << ", ";
        }
        return out << "}";
    }
};
template<class T>
struct graph{
    using Weight_t = T;
    struct Edge_t{
        int from, to;
        T cost;
    };
    int n;
    vector<Edge_t> edge;
    vector<vector<int>> adj;
    function<bool(int)> ignore;
    graph(int n = 1): n(n), adj(n){
        assert(n >= 1);
    }
    graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
        assert(n >= 1);
        if(undirected){
            for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
        }
        else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
    }
    graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
        assert(n >= 1);
        if(undirected){
            for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
        }
        else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
    }
    graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
        assert(n >= 1);
        for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
    }
    graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
        assert(n >= 1);
        for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
    }
    int operator()(int u, int id) const{
        #ifdef LOCAL
        assert(0 <= id && id < (int)edge.size());
        assert(edge[id].from == u || edge[id].to == u);
        #endif
        return u ^ edge[id].from ^ edge[id].to;
    }
    int link(int u, int v, T w = {}){ // insert an undirected edge
        int id = (int)edge.size();
        adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
        return id;
    }
    int orient(int u, int v, T w = {}){ // insert a directed edge
        int id = (int)edge.size();
        adj[u].push_back(id), edge.push_back({u, v, w});
        return id;
    }
    void clear(){
        for(auto [u, v, w]: edge){
            adj[u].clear();
            adj[v].clear();
        }
        edge.clear();
        ignore = {};
    }
    graph transposed() const{ // the transpose of the directed graph
        graph res(n);
        for(auto &e: edge) res.orient(e.to, e.from, e.cost);
        res.ignore = ignore;
        return res;
    }
    int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
        return (int)adj[u].size();
    }
    // The adjacency list is sorted for each vertex.
    vector<vector<int>> get_adjacency_list() const{
        vector<vector<int>> res(n);
        for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
            if(ignore && ignore(id)) continue;
            res[(*this)(u, id)].push_back(u);
        }
        return res;
    }
    void set_ignoration_rule(const function<bool(int)> &f){
        ignore = f;
    }
    void reset_ignoration_rule(){
        ignore = nullptr;
    }
    friend ostream &operator<<(ostream &out, const graph &g){
        for(auto id = 0; id < (int)g.edge.size(); ++ id){
            if(g.ignore && g.ignore(id)) continue;
            auto &e = g.edge[id];
            out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
        }
        return out;
    }
};
// Requires graph
template<class T>
struct bfs_forest{
    int n;
    T base_dist;
    vector<T> dist;
    vector<int> pv;
    vector<int> pe;
    vector<int> order;
    vector<int> pos;
    vector<int> size;
    vector<int> root_of;
    vector<int> root;
    vector<int> depth;
    vector<int> was;
    bfs_forest(T base_dist = 0): base_dist(base_dist){ }
    void init(int n){
        this->n = n;
        pv.assign(n, -1);
        pe.assign(n, -1);
        order.clear();
        pos.assign(n, -1);
        size.assign(n, -1);
        root_of.assign(n, -1);
        root.clear();
        depth.assign(n, -1);
        dist.assign(n, base_dist);
        was.assign(n, -2);
        attempt = -1;
    }
    int attempt;
    vector<int> q;
    // O(# of nodes reachable from src)
    template<class F = plus<>>
    void _bfs(const graph<T> &g, const vector<int> &src, F UT = plus<>()){
        q = src;
        for(auto u: src){
            assert(was[u] != attempt);
            was[u] = attempt;
            depth[u] = 0;
            dist[u] = base_dist;
            root_of[u] = u;
            root.push_back(u);
            pv[u] = -1;
            pe[u] = -1;
        }
        int init_size = (int)order.size();
        for(auto it = 0; it < (int)q.size(); ++ it){
            int u = q[it];
            pos[u] = (int)order.size();
            order.push_back(u);
            size[u] = 1;
            for(auto id: g.adj[u]){
                if(g.ignore && g.ignore(id)) continue;
                int v = g(u, id);
                if(was[v] == attempt) continue;
                was[v] = attempt;
                depth[v] = depth[u] + 1;
                dist[v] = UT(g.edge[id].cost, dist[u]);
                pv[v] = u;
                pe[v] = id;
                root_of[v] = root_of[u];
                q.push_back(v);
            }
        }
        for(auto i = (int)order.size() - 1; i >= init_size; -- i){
            int u = order[i];
            if(~pv[u]) size[pv[u]] += size[u];
        }
        q.clear();
    }
    // O(# of nodes reachable from src)
    template<class F = plus<>>
    void bfs(const graph<T> &g, const vector<int> &src, F UT = plus<>()){
        assert(g.n <= n);
        root.clear(), order.clear();
        for(auto u: src) assert(0 <= u && u < g.n);
        ++ attempt;
        _bfs(g, src, UT);
    }
    // O(n + m)
    template<class U, class F = plus<>>
    void bfs_all(const graph<U> &g, F UT = plus<>()){
        assert(g.n <= n);
        root.clear(), order.clear();
        ++ attempt;
        for(auto u = 0; u < g.n; ++ u) if(was[u] != attempt) _bfs(g, {u}, UT);
    }
    // Check if u is visited during the last bfs-like call.
    bool visited(int u) const{
        assert(0 <= u && u < n);
        return was[u] == attempt;
    }
    vector<int> get_path(int u, int v) const{
        assert(visited(u) && visited(v) && root_of[u] == root_of[v]);
        vector<int> left, right;
        while(u != v){
            if(depth[u] >= depth[v]){
                left.push_back(u);
                u = pv[u];
            }
            else{
                right.push_back(v);
                v = pv[v];
            }
        }
        left.push_back(u);
        left.insert(left.end(), right.rbegin(), right.rend());
        return left;
    }
};
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(ios::badbit | ios::failbit);
    int n, m, from, to, len;
    cin >> n >> m >> from >> to >> len, -- from, -- to;
    auto _f = [&](string s)->void{
        cout << s << endl;
        exit(0);
    };
    auto yes = [&]()->void{
        _f("Yes");
    };
    auto no = [&]()->void{
        _f("No");
    };
    auto unknown = [&]()->void{
        _f("Unknown");
    };
    disjoint_set dsu(n << 1);
    graph<int> g(n);
    for(auto i = 0; i < m; ++ i){
        int u, v;
        cin >> u >> v, -- u, -- v;
        dsu.merge(u << 1, v << 1 | 1);
        dsu.merge(u << 1 | 1, v << 1);
        g.link(u, v);
    }
    bfs_forest<int> bf;
    bf.init(n);
    bf.bfs(g, {from});
    if(from == to){
        if(len & 1){
            no();
        }
        bf.size[from] >= 2 ? yes() : n == 1 ? no() : unknown();
    }
    if(n == 2){
        if(~len & 1){
            no();
        }
        bf.size[from] >= 2 ? yes() : unknown();
    }
    if(dsu.share(from << 1, to << 1)){
        if(len & 1){
            no();
        }
        bf.depth[to] == len || bf.depth[to] < len && bf.size[from] >= 2 ? yes() : unknown();
    }
    else if(dsu.share(from << 1, to << 1 | 1)){
        if(~len & 1){
            no();
        }
        bf.depth[to] == len || bf.depth[to] < len && bf.size[from] >= 2 ? yes() : unknown();
    }
    else{
        unknown();
    }
    return 0;
}
/*
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0