Submission #3017899

---

Source Code Expand

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

typedef pair<int, int> Pair;

struct BCC{
    vector<Pair> bridge;
    vector<vector<int>> each_bcc;
    vector<int> cmp;
    stack<int> roots;
    stack<int> S;
    vector<bool> inS;
    vector<int> order;
    int k;

    void visit(int cur, int pre, const vector<int> G[]){
        order[cur] = ++k;
        S.push(cur);
        inS[cur] = true;
        roots.push(cur);

        for(auto to : G[cur]){
            if(order[to] == 0){
                visit(to, cur, G);
            }else if(to != pre && inS[to]){
                while(order[roots.top()] > order[to]) roots.pop();
            }
        }

        if(cur == roots.top()){
            if(pre != -1) bridge.push_back({pre, cur});
            vector<int> bcc;
            while(true){
                int node = S.top();
                S.pop();
                inS[node] = false;
                bcc.push_back(node);
                cmp[node] = each_bcc.size();
                if(node == cur) break;
            }
            each_bcc.push_back(bcc);
            roots.pop();
        }
    }

    void calculate(int N, const vector<int> edges[]){
        order.resize(N, 0);
        inS.resize(N, false);
        cmp.resize(N, 0);
        k = 0;
        for(int i=0; i<N; i++){
            if(order[i] == 0) visit(i, -1, edges);
        }
    }

    int dump_graph(int N, const vector<int> edges[], vector<int> edges2[]){
        for(int i=0; i<N; i++){
            for(auto j : edges[i]){
                if(cmp[i] != cmp[j]){
                    edges2[cmp[i]].push_back(cmp[j]);
                }
            }
        }
        return *max_element(cmp.begin(), cmp.end()) + 1;  
    }
};

struct LCA{
    static const int BITLEN = 30;
    vector<int> parent[BITLEN];
    vector<int> depth;
    int bitlen;

    void initialize(int N, const vector<int> edges[]){
        int root = 0;
        bitlen = 1;
        while((1<<bitlen) < N) bitlen <<= 1;
        for(int i=0; i<bitlen; i++) parent[i].resize(N);
        depth.resize(N, -1);

        dfs(root, -1, 0, edges);
        for(int k=0; k<bitlen-1; k++){
            for(int v=0; v<N; v++){
                if(depth[v] == -1) continue;
                if(parent[k][v] < 0){
                    parent[k+1][v] = -1;
                }else{
                    parent[k+1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    void dfs(int v, int p, int d, const vector<int> edges[]){
        parent[0][v] = p;
        depth[v] = d;
        for(auto u : edges[v]){
            if(u != p) dfs(u, v, d+1, edges);
        }
    }

    int lca(int u, int v){
        if(depth[u] > depth[v]) swap(u, v);
        for(int k=0; k<bitlen; k++){
            if( ((depth[v]-depth[u]) >> k) & 1 ) v = parent[k][v];
        }
        if(u == v) return u;
        for(int k=bitlen-1; k>=0; k--){
            if(parent[k][u] != parent[k][v]){
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }

    int dist(int u, int v){
        int l = lca(u, v);
        return depth[u] + depth[v] - depth[l]*2;
    }
};

int main(){
    int i, j, k;
    int N, M;
    cin >> N >> M;
    const int MAX = 100000;
    vector<int> edges[MAX];
    for(i=0; i<M; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        edges[x-1].push_back(y-1);
        edges[y-1].push_back(x-1);
    }

    BCC bcc;
    bcc.calculate(N, edges);
    vector<int> edges2[MAX];
    int N2 = bcc.dump_graph(N, edges, edges2);
    LCA lca;
    lca.initialize(N2, edges2);

    int Q;
    cin >> Q;
    for(i=0; i<Q; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        a = bcc.cmp[a-1];
        b = bcc.cmp[b-1];
        c = bcc.cmp[c-1];
        int d1 = lca.dist(a, c);
        int d2 = lca.dist(a, b) + lca.dist(b, c);
        printf("%s\n", (d1==d2 ? "OK" : "NG"));
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:131:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
                               ^
./Main.cpp:147:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
                                      ^

Judge Result