Submission #5327273

---

Source Code Expand

#!/usr/bin/env python3
import sys

sys.setrecursionlimit(101010)


class UnionFind():
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        while 0 <= self.table[x]:
            x = self.table[x]
        return x

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        r = rx
        if rx != ry:
            dx = -self.table[rx]
            dy = -self.table[ry]
            if dx != dy:
                if dx < dy:
                    self.table[rx] = ry
                    r = ry
                else:
                    self.table[ry] = rx
            else:
                self.table[rx] -= 1
                self.table[ry] = rx
        return r


INT_MAX = 10 ** 20
n0 = None


class SegTree:

    def __init__(self, n):
        global n0

        self.n = n0 = n
        self.dat = [INT_MAX] * (n * 2)


    def update(self, i, x):
        i += self.n - 1
        self.dat[i] = x
        while 0 < i:
            i = (i - 1) // 2
            self.dat[i] = min(self.dat[i * 2 + 1], self.dat[i * 2 + 2])


    def query(self, a, b, k = 0, l = 0, r = None):
        if r is None:
            r = n0
        if r <= a or b <= l:
            return INT_MAX
        if a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)


def dfs(g, res, v, count, p, low, pre):
    pre[v] = count
    low[v] = count
    count += 1
    for w in g[v]:
        if pre[w] == -1:
            r, count = dfs(g, res, w, count, v, low, pre)
            low[v] = min(low[v], r)
            if low[w] == pre[w]:
                res.add((v, w))
                res.add((w, v))
        else:
            if p == w:
                continue
            low[v] = min(low[v], low[w])

    return low[v], count


def dfs2(tree, v, count, d, pos, depth, seg):
    pos[v] = count
    depth[v] = d
    seg.update(count, d)
    count += 1
    for w in tree[v]:
        if pos[w] == -1:
            count = dfs2(tree, w, count, d + 1, pos, depth, seg)
            pos[v] = count
            seg.update(count, d)
            count += 1

    return count


def solve(n, m, g, q, qry):

    pre = [-1] * n
    low = [-1] * n
    bridges = set()
    dfs(g, bridges, 0, 0, -1, low, pre)


    uf = UnionFind(n)
    for v in range(n):
        for w in g[v]:
            if v < w:
                if not (v, w) in bridges:
                    uf.unite(v, w)


    tree = [[] for _ in range(n)]
    for p in bridges:
        v, w = p
        rv = uf.find(v)
        rw = uf.find(w)
        tree[rv].append(rw)
        tree[rw].append(rv)
    r = -1
    for v in range(n):
        if len(tree[v]):
            r = v
            break


    if r == -1:
        for _ in qry:
            print('OK')
        return


    pos = [-1] * n
    depth = [-1] * n
    seg = SegTree(2 ** 18)
    dfs2(tree, r, 0, 0, pos, depth, seg)


    for t in qry:
        a, b, c = t
        ra = uf.find(a)
        rb = uf.find(b)
        rc = uf.find(c)
        if ra == rb or rb == rc:
            print('OK')
        elif ra == rc:
            print('NG')
        else:
            pa = pos[ra]
            pb = pos[rb]
            pc = pos[rc]
            ab = depth[ra] + depth[rb] - 2 * seg.query(min(pa, pb), max(pa, pb) + 1)
            bc = depth[rb] + depth[rc] - 2 * seg.query(min(pb, pc), max(pb, pc) + 1)
            ac = depth[ra] + depth[rc] - 2 * seg.query(min(pa, pc), max(pa, pc) + 1)
            print('OK' if ac == ab + bc else 'NG')


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    g = [[] for _ in range(n)]
    for _ in range(m):
        x, y = input().split()
        x = int(x) - 1
        y = int(y) - 1
        g[x].append(y)
        g[y].append(x)
    q = input()
    q = int(q)
    qry = []
    for _ in range(q):
        a, b, c = input().split()
        a = int(a) - 1
        b = int(b) - 1
        c = int(c) - 1
        qry.append((a, b, c))


    solve(n, m, g, q, qry)


if __name__ == '__main__':
    main()

Submission Info

Judge Result