Submission #1766366

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <iomanip>
using namespace std;
  
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define RREP(i,n) for(int (i)=(int)(n)-1;i>=0;i--)
#define REMOVE(Itr,n) (Itr).erase(remove((Itr).begin(),(Itr).end(),n),(Itr).end())
typedef long long ll;
 
struct LowLink {
    
    vector < vector < int > > G;
    vector < int > ord, low;
    vector < bool > used;
    vector < pair < int, int > > bridge;
    vector < int > articulation_point;
    const int INF = 1145141919;
    
    LowLink (int n) : G(n), ord(n), low(n), used(n) {}
    
    void add_edge(int a, int b) {
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    void build(int root) {
        fill(low.begin(), low.end(), INF);
        fill(used.begin(), used.end(), false);
        dfs(root, -1, 1);
    }
    
    int dfs(int v, int prev, int cnt) {
        used[v] = true;
        low[v] = ord[v] = cnt;
        int min_low = cnt;
        int route = 0;
        bool isArticulation = false;
        for (int i = 0; i < G[v].size(); i++) {
            if (!used[G[v][i]]) {
                route++;
                int low_nxt = dfs(G[v][i], v, cnt + 1);
                if (ord[v] < low_nxt) {
                    bridge.push_back(make_pair(v, G[v][i]));
                }
                if (prev != -1 && G[v].size() >= 2 && low_nxt >= cnt) {
                    isArticulation = true;
                }
                min_low = min(min_low, low_nxt);
            } else if (G[v][i] != prev) {
                min_low = min(min_low, low[G[v][i]]);
            }
        }
        if (prev == -1 && route > 1) isArticulation = true;
        if (isArticulation) articulation_point.push_back(v);
        return low[v] = min_low;
    }
    
};

struct UnionFind {
    
    vector < int > node;
    UnionFind(int n) : node(n, -1) {}
    
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (node[y] < node[x]) swap(x, y);
            node[x] += node[y];
            node[y] = x;
        }
        return x != y;
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    int root(int x) {
        return node[x] < 0 ? x : node[x] = root(node[x]);
    }
    
    int size(int x) {
        return -node[root(x)];
    }
    
};
 
struct LCA {
    
    int N,LOG_N;
    vector< vector< int > > parent;
    vector< vector< int > > G;
    vector< int > depth;
    
    LCA (int n) : N(n), depth(n), G(n), LOG_N((int)(log2(n)+1)) {
        parent = vector< vector< int > >(LOG_N, vector<int>(N));
    }
    
    void add_edge(int a, int b) {
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    void init(int root) {
        dfs(root, -1, 0);
        for (int k = 0; k + 1 < LOG_N; k++) {
            for (int v = 0; v < N; v++) {
                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) {
        parent[0][v] = p;
        depth[v] = d;
        for (int i = 0; i < G[v].size(); i++) {
            if (G[v][i] != p) dfs(G[v][i], v, d+1);
        }
    }
    
    int dist(int a, int b) {
        int par = getParent(a,b);
        return depth[a] + depth[b] - depth[par] * 2;
    }
    
    int getParent(int u, int v) {
        if (depth[u] > depth[v]) swap(u,v);
        for (int k = 0; k < LOG_N; k++) {
            if (((depth[v] - depth[u]) >> k) & 1) v = parent[k][v];
        }
        if (u == v) return u;
        for (int k = LOG_N - 1; k >= 0; k--) {
            if(parent[k][u] != parent[k][v]){
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
    
};
 
 
int N,M;
vector < pair < int,int > > edge;
set < pair < int, int > > bridge;
LowLink inst(100010);
UnionFind UF(100010);
LCA lca(100010);
 
int main() {
    
    cin >> N >> M;
    REP(i,M) {
        int a,b; cin >> a >> b;
        inst.add_edge(a, b);
        edge.push_back(make_pair(a,b));
    }
    
    inst.build(1);
    REP(i,inst.bridge.size()) {
        pair < int,int > e = inst.bridge[i];
        bridge.insert(e);
        swap(e.first, e.second);
        bridge.insert(e);
    }
    
    REP(i,M) {
        if (bridge.find(edge[i]) == bridge.end()) {
            UF.unite(edge[i].first, edge[i].second);
        }
    }
    
    int r = 0;
    REP(i,M) {
        int a = UF.root(edge[i].first);
        int b = UF.root(edge[i].second);
        if (a != b) {
            lca.add_edge(a, b);
            r = a;
        }
    }
    
    lca.init(r);
    
    int Q; cin >> Q;
    REP(kai,Q) {
        int A,B,C; cin >> A >> B >> C;
        A = UF.root(A);
        B = UF.root(B);
        C = UF.root(C);
        int d1 = lca.dist(A, C);
        int d2 = lca.dist(A, B) + lca.dist(B, C);
        if (d1 == d2) {
            cout << "OK" << endl;
        } else {
            cout << "NG" << endl;
        }
    }
    
    return 0;
}

Submission Info

Judge Result