Submission #1756481

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, M, Q;
vector<int> G[100000], G2[100000], G3[100000];

bool used[100000];
int T[100000], ord[100000], R[100000];
int U[20][100000];

void dfs(int x, int p, int r) {
  used[x] = true;
  R[x] = r;
  for (int t : G[x]) {
    if (t == p) continue;
    if (used[t]) {
      if (R[t] > R[x]) {
        T[t]++;
        T[x]--;
      }
      continue;
    }
    dfs(t, x, r+1);
  }
}

int dfs2(int x, int p) {
  used[x] = true;
  int s = T[x];
  for (int t : G[x]) {
    if (t == p) continue;
    if (used[t]) continue;
    s += dfs2(t, x);
  }
  if (s) G2[x].pb(p), G2[p].pb(x);
  return s;
}

void dfs3(int x, int p, int k) {
  ord[x] = k;
  for (int t : G2[x]) {
    if (t == p) continue;
    dfs3(t, x, k);
  }
}
void dfs4(int x, int p, int r) {
  R[x] = r;
  U[0][x] = p;
  for (int t : G3[x]) {
    if (t == p) continue;
    dfs4(t, x, r+1);
  }
}

int lca(int x, int y) {
  if (R[x] < R[y]) swap(x, y);
  for (int k=19; k>=0; k--) if (R[x]-R[y] >= 1<<k) x = U[k][x];
  if (x == y) return x;
  for (int k=19; k>=0; k--) if (U[k][x] != U[k][y]) x = U[k][x], y = U[k][y];
  return U[0][x];
}

int dist(int x, int y) {
  return R[x] + R[y] - 2*R[lca(x, y)];
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> M;
  rep(i, M) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  dfs(0, -1, 0);
  rep(i, N) used[i] = false;
  dfs2(0, -1);

  rep(i, N) ord[i] = -1;
  int k = 0;
  rep(i, N) if (ord[i] == -1) dfs3(i, -1, k++);
  rep(x, N) {
    for (int t : G[x]) {
      if (ord[x] == ord[t]) continue;
      G3[ord[x]].pb(ord[t]);
      G3[ord[t]].pb(ord[x]);
    }
  }
  rep(x, k) sort(all(G3[x])), uniq(G3[x]);
  dfs4(0, -1, 0);
  rep(k, 19) rep(i, N) {
    if (U[k][i] == -1) U[k+1][i] = -1;
    else U[k+1][i] = U[k][U[k][i]];
  }

  cin >> Q;
  rep(_, Q) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--, c--;
    a = ord[a], b = ord[b], c = ord[c];
    if (dist(a, b) + dist(b, c) == dist(a, c)) cout << "OK\n";
    else cout << "NG\n";
  }
  return 0;
}

Submission Info

Judge Result