Submit Info #24685

Problem Lang User Status Time Memory
Dominator Tree pypy3 toyuzuko Hacked(WA) 912 ms 89.55 MiB

ケース詳細
Name Status Time Memory
example_00 AC 49 ms 29.47 MiB
example_01 AC 49 ms 29.54 MiB
gen_tree_00 WA 576 ms 78.44 MiB
gen_tree_01 WA 554 ms 77.18 MiB
gen_tree_02 WA 663 ms 83.54 MiB
gen_tree_2_00 WA 893 ms 86.34 MiB
gen_tree_2_01 WA 912 ms 89.55 MiB
gen_tree_2_02 WA 863 ms 89.39 MiB
random_00 AC 115 ms 53.76 MiB
random_01 AC 221 ms 68.34 MiB
random_02 AC 97 ms 42.07 MiB
random_03 AC 128 ms 56.32 MiB
random_04 AC 67 ms 32.07 MiB

class DSUQuery(): def __init__(self, n, f, op): self.n = n self.par = [i for i in range(n)] self.m = [i for i in range(n)] self.f = f self.op = op def find(self, v): if self.par[v] == v: return v r = self.find(self.par[v]) fv = self.f(self.m[v]) fp = self.f(self.m[self.par[v]]) if self.op(fv, fp) == fp: self.m[v] = self.m[self.par[v]] self.par[v] = r return r def eval(self, v): self.find(v) return self.m[v] def link(self, v, p): self.par[v] = p class DiGraph(): def __init__(self, n): self.n = n self.graph = [[] for _ in range(n)] self.rev = [[] for _ in range(n)] def add_edge(self, fr, to, idx=1): self.graph[fr - idx].append(to - idx) self.rev[to - idx].append(fr - idx) def dfs(self, r): self.par = [None] * self.n self.ord = [] self.ind = [None] * self.n stack = [r] while stack: v = stack.pop() self.ind[v] = len(self.ord) self.ord.append(v) for adj in self.graph[v]: if self.ind[adj] is not None: continue self.par[adj] = v stack.append(adj) def dominator_tree(self, r): bucket = [[] for _ in range(self.n)] idom = [0] * self.n u = [0] * self.n self.dfs(r) uf = DSUQuery(self.n, lambda x: self.ind[x], min) for w in self.ord[1:][::-1]: for v in self.rev[w]: if self.par[v] is None: continue e = uf.eval(v) self.ind[w] = min(self.ind[w], self.ind[e]) bucket[self.ord[self.ind[w]]].append(w) for v in bucket[self.par[w]]: u[v] = uf.eval(v) bucket[self.par[w]].clear() uf.link(w, self.par[w]) for w in self.ord[1:]: v = u[w] if self.ind[w] == self.ind[v]: idom[w] = self.ind[w] else: idom[w] = idom[v] for w in self.ord[1:]: idom[w] = self.ord[idom[w]] for v in range(self.n): if self.par[v] is None: if v == r: idom[v] = v else: idom[v] = -1 return idom import sys input = sys.stdin.buffer.readline N, M, S = map(int, input().split()) dg = DiGraph(N) for _ in range(M): a, b = map(int, input().split()) dg.add_edge(a, b, 0) print(*dg.dominator_tree(S))