Submit Info #20771

Problem Lang User Status Time Memory
Dominator Tree java dalt AC 218 ms 54.45 MiB

ケース詳細
Name Status Time Memory
example_00 AC 66 ms 19.43 MiB
example_01 AC 60 ms 19.48 MiB
random_00 AC 156 ms 42.29 MiB
random_01 AC 218 ms 54.45 MiB
random_02 AC 133 ms 31.15 MiB
random_03 AC 181 ms 49.02 MiB
random_04 AC 93 ms 22.76 MiB

import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.util.Arrays; import java.io.IOException; import java.util.ArrayList; import java.io.UncheckedIOException; import java.util.List; import java.io.Closeable; import java.io.Writer; import java.io.OutputStreamWriter; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) throws Exception { Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29); thread.start(); thread.join(); } static class TaskAdapter implements Runnable { @Override public void run() { InputStream inputStream = System.in; OutputStream outputStream = System.out; FastInput in = new FastInput(inputStream); FastOutput out = new FastOutput(outputStream); DominatorTree solver = new DominatorTree(); solver.solve(1, in, out); out.close(); } } static class DominatorTree { public void solve(int testNumber, FastInput in, FastOutput out) { int n = in.readInt(); int m = in.readInt(); int s = in.readInt(); List<DirectedEdge>[] g = Graph.createDirectedGraph(n); for (int i = 0; i < m; i++) { int a = in.readInt(); int b = in.readInt(); Graph.addEdge(g, a, b); } template_graph_DominatorTree dt = new template_graph_DominatorTree(g, s); for (int i = 0; i < n; i++) { if (i == s) { out.append(s).append(' '); continue; } out.append(dt.parent(i)).append(' '); } } } static class FastOutput implements AutoCloseable, Closeable, Appendable { private StringBuilder cache = new StringBuilder(10 << 20); private final Writer os; public FastOutput append(CharSequence csq) { cache.append(csq); return this; } public FastOutput append(CharSequence csq, int start, int end) { cache.append(csq, start, end); return this; } public FastOutput(Writer os) { this.os = os; } public FastOutput(OutputStream os) { this(new OutputStreamWriter(os)); } public FastOutput append(char c) { cache.append(c); return this; } public FastOutput append(int c) { cache.append(c); return this; } public FastOutput flush() { try { os.append(cache); os.flush(); cache.setLength(0); } catch (IOException e) { throw new UncheckedIOException(e); } return this; } public void close() { flush(); try { os.close(); } catch (IOException e) { throw new UncheckedIOException(e); } } public String toString() { return cache.toString(); } } static class IntegerMultiWayStack { private int[] values; private int[] next; private int[] heads; private int alloc; private int stackNum; public IntegerIterator iterator(final int queue) { return new IntegerIterator() { int ele = heads[queue]; public boolean hasNext() { return ele != 0; } public int next() { int ans = values[ele]; ele = next[ele]; return ans; } }; } private void doubleCapacity() { int newSize = Math.max(next.length + 10, next.length * 2); next = Arrays.copyOf(next, newSize); values = Arrays.copyOf(values, newSize); } public void alloc() { alloc++; if (alloc >= next.length) { doubleCapacity(); } next[alloc] = 0; } public boolean isEmpty(int qId) { return heads[qId] == 0; } public IntegerMultiWayStack(int qNum, int totalCapacity) { values = new int[totalCapacity + 1]; next = new int[totalCapacity + 1]; heads = new int[qNum]; stackNum = qNum; } public void addLast(int qId, int x) { alloc(); values[alloc] = x; next[alloc] = heads[qId]; heads[qId] = alloc; } public String toString() { StringBuilder builder = new StringBuilder(); for (int i = 0; i < stackNum; i++) { if (isEmpty(i)) { continue; } builder.append(i).append(": "); for (IntegerIterator iterator = iterator(i); iterator.hasNext(); ) { builder.append(iterator.next()).append(","); } if (builder.charAt(builder.length() - 1) == ',') { builder.setLength(builder.length() - 1); } builder.append('\n'); } return builder.toString(); } } static class DirectedEdge { public int to; public DirectedEdge(int to) { this.to = to; } public String toString() { return "->" + to; } } static class template_graph_DominatorTree { List<? extends DirectedEdge>[] g; IntegerMultiWayStack in; List<DirectedEdge>[] span; int[] depth; int[] begin; int[] end; int[] invDfn; int[] sdom; int[] idom; int root; int[] stk; template_graph_DominatorTree.Segment segment; template_graph_DominatorTree.SegmentQuery sq = new template_graph_DominatorTree.SegmentQuery(); private int order = 0; public template_graph_DominatorTree(List<? extends DirectedEdge>[] g, int root) { this.root = root; this.g = g; this.span = Graph.createDirectedGraph(g.length); sdom = new int[g.length]; idom = new int[g.length]; Arrays.fill(idom, -1); depth = new int[g.length]; stk = new int[g.length]; end = new int[g.length]; segment = new template_graph_DominatorTree.Segment(0, g.length); int len = 0; for (List<?> list : g) { len += list.size(); } in = new IntegerMultiWayStack(g.length, len); begin = new int[g.length]; generateTree1(root, -1); invDfn = new int[g.length + 1]; for (int i = 0; i < g.length; i++) { invDfn[begin[i]] = i; } for (int i = 0; i < g.length; i++) { if (begin[i] == 0) { continue; } for (DirectedEdge e : g[i]) { in.addLast(e.to, i); } } dfsForSdom(root); dfsForIdom(root); idom[root] = -1; //debug.debug("idom", idom); //debug.debug("sdom", sdom); //debug.debug("span", span); } public int parent(int i) { return idom[i]; } private void dfsForIdom(int root) { stk[depth[root]] = root; segment.update(depth[root], depth[root], 0, span.length, begin[sdom[root]]); sq.reset(); segment.query(depth[sdom[root]] + 1, depth[root], 0, span.length, sq); int u = stk[sq.index]; if (sdom[root] == sdom[u]) { idom[root] = sdom[root]; } else { idom[root] = idom[u]; } for (DirectedEdge e : span[root]) { dfsForIdom(e.to); } } private void dfsForSdom(int root) { for (int i = span[root].size() - 1; i >= 0; i--) { DirectedEdge e = span[root].get(i); dfsForSdom(e.to); } int min = begin[root]; for (IntegerIterator iterator = in.iterator(root); iterator.hasNext(); ) { int node = iterator.next(); if (begin[node] < begin[root]) { min = Math.min(min, begin[node]); } else { int candidate = segment.query(begin[node], begin[node], 0, g.length); min = Math.min(min, candidate); } } sdom[root] = invDfn[min]; segment.updateMin(begin[root], end[root], 0, g.length, begin[sdom[root]]); } private void generateTree1(int root, int p) { depth[root] = p == -1 ? 0 : depth[p] + 1; begin[root] = ++order; for (DirectedEdge e : g[root]) { if (e.to == p || begin[e.to] != 0) { continue; } span[root].add(e); generateTree1(e.to, root); } end[root] = order; } public String toString() { return Arrays.toString(idom); } private static class SegmentQuery { int s; int index; public void reset() { s = Integer.MAX_VALUE; index = 0; } public void update(int s, int index) { if (this.s > s) { this.s = s; this.index = index; } } } private static class Segment implements Cloneable { private template_graph_DominatorTree.Segment left; private template_graph_DominatorTree.Segment right; private int s = Integer.MAX_VALUE; private int dirty = Integer.MAX_VALUE; public void pushUp() { s = Math.min(left.s, right.s); } private void modify(int d) { dirty = Math.min(d, dirty); s = Math.min(d, dirty); } public void pushDown() { if (dirty != Integer.MAX_VALUE) { left.modify(dirty); right.modify(dirty); dirty = Integer.MAX_VALUE; } } public Segment(int l, int r) { if (l < r) { int m = DigitUtils.floorAverage(l, r); left = new template_graph_DominatorTree.Segment(l, m); right = new template_graph_DominatorTree.Segment(m + 1, r); pushUp(); } else { } } private boolean covered(int ll, int rr, int l, int r) { return ll <= l && rr >= r; } private boolean noIntersection(int ll, int rr, int l, int r) { return ll > r || rr < l; } public void update(int ll, int rr, int l, int r, int x) { if (noIntersection(ll, rr, l, r)) { return; } if (covered(ll, rr, l, r)) { s = x; return; } pushDown(); int m = DigitUtils.floorAverage(l, r); left.update(ll, rr, l, m, x); right.update(ll, rr, m + 1, r, x); pushUp(); } public void updateMin(int ll, int rr, int l, int r, int x) { if (noIntersection(ll, rr, l, r)) { return; } if (covered(ll, rr, l, r)) { modify(x); return; } pushDown(); int m = DigitUtils.floorAverage(l, r); left.updateMin(ll, rr, l, m, x); right.updateMin(ll, rr, m + 1, r, x); pushUp(); } public void query(int ll, int rr, int l, int r, template_graph_DominatorTree.SegmentQuery q) { if (noIntersection(ll, rr, l, r) || s >= q.s) { return; } if (l == r) { q.update(s, l); return; } pushDown(); int m = DigitUtils.floorAverage(l, r); if (left.s < right.s) { left.query(ll, rr, l, m, q); right.query(ll, rr, m + 1, r, q); } else { right.query(ll, rr, m + 1, r, q); left.query(ll, rr, l, m, q); } } public int query(int ll, int rr, int l, int r) { if (noIntersection(ll, rr, l, r)) { return Integer.MAX_VALUE; } if (covered(ll, rr, l, r)) { return s; } pushDown(); int m = DigitUtils.floorAverage(l, r); return Math.min(left.query(ll, rr, l, m), right.query(ll, rr, m + 1, r)); } private template_graph_DominatorTree.Segment deepClone() { template_graph_DominatorTree.Segment seg = clone(); if (seg.left != null) { seg.left = seg.left.deepClone(); } if (seg.right != null) { seg.right = seg.right.deepClone(); } return seg; } protected template_graph_DominatorTree.Segment clone() { try { return (template_graph_DominatorTree.Segment) super.clone(); } catch (CloneNotSupportedException e) { throw new RuntimeException(e); } } private void toString(StringBuilder builder) { if (left == null && right == null) { builder.append(s).append(","); return; } pushDown(); left.toString(builder); right.toString(builder); } public String toString() { StringBuilder builder = new StringBuilder(); deepClone().toString(builder); if (builder.length() > 0) { builder.setLength(builder.length() - 1); } return builder.toString(); } } } static class DigitUtils { private DigitUtils() { } public static int floorAverage(int x, int y) { return (x & y) + ((x ^ y) >> 1); } } static class FastInput { private final InputStream is; private byte[] buf = new byte[1 << 13]; private int bufLen; private int bufOffset; private int next; public FastInput(InputStream is) { this.is = is; } private int read() { while (bufLen == bufOffset) { bufOffset = 0; try { bufLen = is.read(buf); } catch (IOException e) { bufLen = -1; } if (bufLen == -1) { return -1; } } return buf[bufOffset++]; } public void skipBlank() { while (next >= 0 && next <= 32) { next = read(); } } public int readInt() { int sign = 1; skipBlank(); if (next == '+' || next == '-') { sign = next == '+' ? 1 : -1; next = read(); } int val = 0; if (sign == 1) { while (next >= '0' && next <= '9') { val = val * 10 + next - '0'; next = read(); } } else { while (next >= '0' && next <= '9') { val = val * 10 - next + '0'; next = read(); } } return val; } } static class Graph { public static void addEdge(List<DirectedEdge>[] g, int s, int t) { g[s].add(new DirectedEdge(t)); } public static List<DirectedEdge>[] createDirectedGraph(int n) { List<DirectedEdge>[] ans = new List[n]; for (int i = 0; i < n; i++) { ans[i] = new ArrayList<>(); } return ans; } } static interface IntegerIterator { boolean hasNext(); int next(); } }