結果

問題 No.1983 [Cherry 4th Tune C] 南の島のマーメイド
ユーザー 👑 KazunKazun
提出日時 2022-06-12 19:29:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 424 ms / 4,000 ms
コード長 7,253 bytes
コンパイル時間 4,352 ms
コンパイル使用メモリ 216,780 KB
実行使用メモリ 62,792 KB
最終ジャッジ日時 2024-04-17 12:34:31
合計ジャッジ時間 14,498 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 6 ms
5,376 KB
testcase_09 AC 13 ms
5,376 KB
testcase_10 AC 10 ms
5,504 KB
testcase_11 AC 11 ms
5,504 KB
testcase_12 AC 9 ms
5,376 KB
testcase_13 AC 204 ms
22,508 KB
testcase_14 AC 201 ms
28,460 KB
testcase_15 AC 246 ms
30,832 KB
testcase_16 AC 102 ms
26,524 KB
testcase_17 AC 200 ms
30,392 KB
testcase_18 AC 209 ms
30,848 KB
testcase_19 AC 250 ms
39,896 KB
testcase_20 AC 209 ms
29,480 KB
testcase_21 AC 175 ms
31,712 KB
testcase_22 AC 274 ms
37,420 KB
testcase_23 AC 299 ms
44,392 KB
testcase_24 AC 371 ms
44,384 KB
testcase_25 AC 343 ms
44,388 KB
testcase_26 AC 338 ms
44,260 KB
testcase_27 AC 268 ms
44,388 KB
testcase_28 AC 309 ms
44,260 KB
testcase_29 AC 328 ms
44,392 KB
testcase_30 AC 346 ms
44,264 KB
testcase_31 AC 291 ms
44,264 KB
testcase_32 AC 348 ms
44,136 KB
testcase_33 AC 2 ms
5,376 KB
testcase_34 AC 337 ms
26,060 KB
testcase_35 AC 424 ms
62,792 KB
testcase_36 AC 387 ms
34,668 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 56 ms
5,376 KB
testcase_39 AC 190 ms
62,236 KB
testcase_40 AC 155 ms
38,852 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

struct Edge{
    int id, source, target;

    Edge(int id, int source, int target): id(id), source(source), target(target){}

    // 出力
    friend ostream &operator<<(ostream &os, const Edge &e) {
        return os << "id: " << e.id << ", source: " << e.source << ", target: " << e.target;
    }
};

struct Graph{
    using E=Edge;
    vector<vector<E>> inc;
    vector<E> edge;

    Graph(int N=0){
        inc.resize(N);
    }

    // 頂点数
    int order(){return inc.size();}

    // 辺の数
    int size(){return edge.size();}

    // 頂点を1個追加する.
    int add_vertex(){
        inc.emplace_back(vector<E>());
        return inc.size()-1;
    }

    // 頂点をk個追加する.
    vector<int> add_vertices(int k){
        vector<int> I;
        for (; k--; k>=0){
            I.emplace_back(add_vertex());
        }
        return I;
    }

    // 無向辺 uv を加える.
    int add_edge(int u, int v){
        int i=size();
        inc[u].emplace_back(E(i,u,v));
        inc[v].emplace_back(E(i,v,u));
        edge.emplace_back(E(i,u,v));
        return i;
    }

    // 無向辺 e を加える.
    int add_edge(const Edge &e){
        return add_edge(e.source, e.target);
    }

    // walk を加える.
    vector<int> add_walk(const vector<int> &walk){
        vector<int> J;
        for (int i=0; i<(int)walk.size()-1; i++){
            J.emplace_back(add_edge(walk[i], walk[i+1]));
        }
        return J;
    }

    Edge get_edge(int j){
        return edge[j];
    }

    // cycle を加える.
    vector<int> add_cycle(const vector<int> &cycle){
        vector<int> J=add_walk(cycle);
        J.emplace_back(add_edge(cycle.back(),cycle.front()));
        return J;
    }

    // 頂点 v を含む連結成分を出力する.
    vector<int> connected_component(int v){
        vector<int> C;
        vector<bool> T(order(),false); T[v]=true;
        deque<int> Q{v};

        while (!Q.empty()){
            int x=Q.front(); Q.pop_front();
            C.emplace_back(x);

            for (E &e:inc[x]){
                int t=e.target;
                if (!T[t]){
                    T[t]=true;
                    Q.push_back(t);
                }
            }
        }

        return C;
    }

    // u,v は連結かどうかを求める.
    bool is_connected_vertex(int u, int v){
        if (u==v) return true;

        vector<int> T(order(), false); T[u]=true;
        deque<int> Q{u};

        while (!Q.empty()){
            int x=Q.front(); Q.pop_front();

            for (E &e:inc[x]){
                int t=e.target;
                if (T[t]==false){
                    T[t]=true;
                    Q.push_back(t);

                    if (t==v) return true;
                }
            }
        }

        return false;
    }

    // 2 頂点 u,v 間の距離を求める.
    int distance(int u, int v){
        if (u==v) return 0;

        vector<int> T(order(),-1); T[u]=0;
        deque<int> Q{u};

        while (!Q.empty()){
            int x=Q.front(); Q.pop_front();

            for (E &e:inc[x]){
                int t=e.target;
                if (T[t]==-1){
                    T[t]=T[x]+1;
                    Q.push_back(t);

                    if (t==v) return T[t];
                }
            }
        }

        return -1;
    }

    // 頂点 u 間からの距離を求める.
    vector<int> distance_all(int u){
        vector<int> T(order(),-1); T[u]=0;
        deque<int> Q{u};

        while (!Q.empty()){
            int x=Q.front(); Q.pop_front();

            for (E &e:inc[x]){
                int t=e.target;
                if (T[t]==-1){
                    T[t]=T[x]+1;
                    Q.push_back(t);
                }
            }
        }

        return T;
    }

    // u-v 間の最短路を求める (存在しない場合, []).
    vector<int> shortest_path(int u, int v){
        if (u==v) return vector<int>{u};

        vector<int> T(order(),-1);
        deque<int> Q{u};

        while (!Q.empty()){
            int x=Q.front(); Q.pop_front();

            for (auto &e:inc[x]){
                int y=e.target;
                if (T[y]==-1){
                    T[y]=x;
                    Q.push_back(y);

                    if (y==v){
                        vector<int> P{v};
                        int a=v;
                        while (a!=u){
                            a=T[a];
                            P.emplace_back(a);
                        }
                        reverse(P.begin(), P.end());
                        return P;
                    }
                }
            }
        }
        return vector<int>{};
    }
};

struct Connected_Component_Decomposition{
    vector<vector<int>> component;
    vector<int> id;

    public:
    Connected_Component_Decomposition(Graph &G){
        calculate(G);
    }

    private:
    int k;
    void calculate(Graph &G){
        int N=G.order();

        component.clear();
        id.assign(N,-1);

        k=0;
        for (int v=0; v<N; v++){
            if (id[v]==-1){
                component.emplace_back(vector<int>());
                dfs(G,v);
                k++;
            }
        }
    }

    void dfs(Graph &G, int v){
        id[v]=k;
        component.back().emplace_back(v);
        for (auto &e: G.inc[v]){
            if (id[e.target]==-1) dfs(G,e.target);
        }
    }

    public:
    inline int component_number() const {return component.size();}
    inline bool is_connected(const int &u, const int &v) const {return id[u]==id[v];}
};

struct Lowlink{
    vector<bool> used, bridge, articulation;
    vector<int> ord, low;

    Lowlink(Graph &G){
        int N=G.order(), M=G.size();
        used.assign(N,false);
        ord.assign(N,0);
        low.assign(N,0);

        bridge.assign(M,false);
        articulation.assign(N,false);

        int k=0;
        for (int i=0; i<N; i++){
            if (!used[i]) k=dfs(G,i,k,-1);
        }
    }

    private:
    int dfs(Graph &G, int v, int k, int par){
        used[v]=true;
        ord[v]=k++;
        low[v]=ord[v];

        bool is_arti=false;
        int child=0;

        for (auto &e:G.inc[v]){
            if (!used[e.target]){
                child++;
                k=dfs(G,e.target,k,v);
                low[v]=min(low[v], low[e.target]);
                if (par!=-1 && ord[v]<=low[e.target]) is_arti=true;
                if (ord[v]<low[e.target]) bridge[e.id]=true;
            }else if (e.target!=par){
                low[v]=min(low[v], ord[e.target]);
            }
        }
        if (par==-1 && child>=2) is_arti=true;
        if (is_arti) articulation[v]=true;
        return k;
    }
};

int main(){
    int N,M,Q;
    cin >> N >> M >> Q;

    Graph G(N+1);
    int u,v;
    for (int j=0; j<M; j++){
        scanf("%d%d",&u,&v);
        G.add_edge(u,v);
    }

    Lowlink L(G);
    Graph H(N+1);
    for (int j=0; j<M; j++){
        if (L.bridge[j]){H.add_edge(G.get_edge(j));}
    }

    Connected_Component_Decomposition C(H);
    int x,y;
    for (int q=0; q<Q; q++){
        scanf("%d%d",&x,&y);
        if (C.is_connected(x,y)) cout << "Yes" << "\n";
        else cout << "No" << endl;
    }

}
0