結果
問題 | No.778 クリスマスツリー |
ユーザー | amotoma3 |
提出日時 | 2019-10-05 14:37:18 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,289 ms / 2,000 ms |
コード長 | 12,996 bytes |
コンパイル時間 | 2,282 ms |
コンパイル使用メモリ | 79,812 KB |
実行使用メモリ | 96,108 KB |
最終ジャッジ日時 | 2024-10-14 02:01:35 |
合計ジャッジ時間 | 10,812 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 51 ms
36,988 KB |
testcase_01 | AC | 52 ms
37,032 KB |
testcase_02 | AC | 52 ms
36,844 KB |
testcase_03 | AC | 53 ms
36,892 KB |
testcase_04 | AC | 53 ms
36,856 KB |
testcase_05 | AC | 52 ms
36,840 KB |
testcase_06 | AC | 1,289 ms
96,108 KB |
testcase_07 | AC | 540 ms
74,268 KB |
testcase_08 | AC | 822 ms
85,044 KB |
testcase_09 | AC | 701 ms
74,060 KB |
testcase_10 | AC | 697 ms
74,380 KB |
testcase_11 | AC | 695 ms
74,220 KB |
testcase_12 | AC | 722 ms
73,732 KB |
testcase_13 | AC | 532 ms
74,208 KB |
testcase_14 | AC | 1,279 ms
95,868 KB |
ソースコード
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Arrays; import java.io.BufferedWriter; import java.util.InputMismatchException; import java.io.IOException; 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) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); OutputWriter out = new OutputWriter(outputStream); Task778 solver = new Task778(); solver.solve(1, in, out); out.close(); } static class Task778 { Graph g; BinaryTrie trie = new BinaryTrie(); long ans = 0; public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); g = new BidirectionalGraph(n); for (int i = 0; i < n - 1; i++) { g.addSimpleEdge(in.readInt(), i + 1); } dfs(0, -1); out.printLine(ans); } void dfs(int x, int p) { ans += trie.count(x); trie.insert(x); for (int i = g.firstOutbound(x); i >= 0; i = g.nextOutbound(i)) { int to = g.destination(i); if (to == p) continue; dfs(to, x); } trie.erase(x); } } static interface Edge { } static class OutputWriter { private final PrintWriter writer; public OutputWriter(OutputStream outputStream) { writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); } public OutputWriter(Writer writer) { this.writer = new PrintWriter(writer); } public void close() { writer.close(); } public void printLine(long i) { writer.println(i); } } static class InputReader { private InputStream stream; private byte[] buf = new byte[1024]; private int curChar; private int numChars; private InputReader.SpaceCharFilter filter; public InputReader(InputStream stream) { this.stream = stream; } public int read() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) { return -1; } } return buf[curChar++]; } public int readInt() { int c = read(); while (isSpaceChar(c)) { c = read(); } int sgn = 1; if (c == '-') { sgn = -1; c = read(); } int res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = read(); } while (!isSpaceChar(c)); return res * sgn; } public boolean isSpaceChar(int c) { if (filter != null) { return filter.isSpaceChar(c); } return isWhitespace(c); } public static boolean isWhitespace(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } public interface SpaceCharFilter { public boolean isSpaceChar(int ch); } } static class BidirectionalGraph extends Graph { public int[] transposedEdge; public BidirectionalGraph(int vertexCount) { this(vertexCount, vertexCount); } public BidirectionalGraph(int vertexCount, int edgeCapacity) { super(vertexCount, 2 * edgeCapacity); transposedEdge = new int[2 * edgeCapacity]; } public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) { int lastEdgeCount = edgeCount; super.addEdge(fromID, toID, weight, capacity, reverseEdge); super.addEdge(toID, fromID, weight, capacity, reverseEdge == -1 ? -1 : reverseEdge + 1); this.transposedEdge[lastEdgeCount] = lastEdgeCount + 1; this.transposedEdge[lastEdgeCount + 1] = lastEdgeCount; return lastEdgeCount; } protected int entriesPerEdge() { return 2; } protected void ensureEdgeCapacity(int size) { if (size > edgeCapacity()) { super.ensureEdgeCapacity(size); transposedEdge = resize(transposedEdge, edgeCapacity()); } } } static class BinaryTrie { public static int BIT_MAX = 60; private Node root; public BinaryTrie() { this.root = new Node(); } public void insert(long val) { add(root, val, BIT_MAX - 1); } public void erase(long val) { sub(root, val, BIT_MAX - 1); } public int lowerBound(long val) { return countLower(root, val, BIT_MAX - 1); } public int upperBound(long val) { return lowerBound(val + 1) - 1; } public int count(long from, long to) { return upperBound(to) - lowerBound(from) + 1; } public int count(long to) { return count(0, to); } private void add(Node node, long val, int b) { node.cnt++; if (b < 0) return; int f = (int) (val >> b & 1); if (node.ch[f] == null) node.ch[f] = new Node(); add(node.ch[f], val, b - 1); } private void sub(Node node, long val, int b) { node.cnt--; if (b < 0) return; int f = (int) (val >> b & 1); if (node.ch[f] == null) throw new RuntimeException(); sub(node.ch[f], val, b - 1); } private int countLower(Node node, long val, int b) { if (node == null || b < 0) return 0; int f = (int) (val >> b & 1); return (f == 1 && node.ch[0] != null ? node.ch[0].cnt : 0) + countLower(node.ch[f], val, b - 1); } class Node { int cnt; Node[] ch = new Node[2]; } } static class Graph { public static final int REMOVED_BIT = 0; protected int vertexCount; protected int edgeCount; private int[] firstOutbound; private int[] firstInbound; private Edge[] edges; private int[] nextInbound; private int[] nextOutbound; private int[] from; private int[] to; private long[] weight; public long[] capacity; private int[] reverseEdge; private int[] flags; public Graph(int vertexCount) { this(vertexCount, vertexCount); } public Graph(int vertexCount, int edgeCapacity) { this.vertexCount = vertexCount; firstOutbound = new int[vertexCount]; Arrays.fill(firstOutbound, -1); from = new int[edgeCapacity]; to = new int[edgeCapacity]; nextOutbound = new int[edgeCapacity]; flags = new int[edgeCapacity]; } public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) { ensureEdgeCapacity(edgeCount + 1); if (firstOutbound[fromID] != -1) { nextOutbound[edgeCount] = firstOutbound[fromID]; } else { nextOutbound[edgeCount] = -1; } firstOutbound[fromID] = edgeCount; if (firstInbound != null) { if (firstInbound[toID] != -1) { nextInbound[edgeCount] = firstInbound[toID]; } else { nextInbound[edgeCount] = -1; } firstInbound[toID] = edgeCount; } this.from[edgeCount] = fromID; this.to[edgeCount] = toID; if (capacity != 0) { if (this.capacity == null) { this.capacity = new long[from.length]; } this.capacity[edgeCount] = capacity; } if (weight != 0) { if (this.weight == null) { this.weight = new long[from.length]; } this.weight[edgeCount] = weight; } if (reverseEdge != -1) { if (this.reverseEdge == null) { this.reverseEdge = new int[from.length]; Arrays.fill(this.reverseEdge, 0, edgeCount, -1); } this.reverseEdge[edgeCount] = reverseEdge; } if (edges != null) { edges[edgeCount] = createEdge(edgeCount); } return edgeCount++; } protected final GraphEdge createEdge(int id) { return new GraphEdge(id); } public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) { if (capacity == 0) { return addEdge(from, to, weight, 0, -1); } else { int lastEdgeCount = edgeCount; addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge()); return addEdge(from, to, weight, capacity, lastEdgeCount); } } protected int entriesPerEdge() { return 1; } public final int addWeightedEdge(int from, int to, long weight) { return addFlowWeightedEdge(from, to, weight, 0); } public final int addSimpleEdge(int from, int to) { return addWeightedEdge(from, to, 0); } protected final int edgeCapacity() { return from.length; } public final int firstOutbound(int vertex) { int id = firstOutbound[vertex]; while (id != -1 && isRemoved(id)) { id = nextOutbound[id]; } return id; } public final int nextOutbound(int id) { id = nextOutbound[id]; while (id != -1 && isRemoved(id)) { id = nextOutbound[id]; } return id; } public final int destination(int id) { return to[id]; } public final boolean flag(int id, int bit) { return (flags[id] >> bit & 1) != 0; } public final boolean isRemoved(int id) { return flag(id, REMOVED_BIT); } protected void ensureEdgeCapacity(int size) { if (from.length < size) { int newSize = Math.max(size, 2 * from.length); if (edges != null) { edges = resize(edges, newSize); } from = resize(from, newSize); to = resize(to, newSize); nextOutbound = resize(nextOutbound, newSize); if (nextInbound != null) { nextInbound = resize(nextInbound, newSize); } if (weight != null) { weight = resize(weight, newSize); } if (capacity != null) { capacity = resize(capacity, newSize); } if (reverseEdge != null) { reverseEdge = resize(reverseEdge, newSize); } flags = resize(flags, newSize); } } protected final int[] resize(int[] array, int size) { int[] newArray = new int[size]; System.arraycopy(array, 0, newArray, 0, array.length); return newArray; } private long[] resize(long[] array, int size) { long[] newArray = new long[size]; System.arraycopy(array, 0, newArray, 0, array.length); return newArray; } private Edge[] resize(Edge[] array, int size) { Edge[] newArray = new Edge[size]; System.arraycopy(array, 0, newArray, 0, array.length); return newArray; } protected class GraphEdge implements Edge { protected int id; protected GraphEdge(int id) { this.id = id; } } } }