Submission #3599412
Source Code Expand
import java.io.*; import java.util.ArrayDeque; import java.util.StringTokenizer; public class Main { static int N; static int[] A, B; public static void main(String[] args) { FastScanner fc = new FastScanner(System.in); N = fc.nextInt(); A = new int[N-1]; B = new int[N-1]; for (int i = 0; i < N - 1; i++) { A[i] = i+1; B[i] = fc.nextInt(); } int[] answer = solve(); PrintWriter pw = new PrintWriter(System.out); for (int i : answer) { pw.println(i); } pw.flush(); } static int[] solve() { // 自分を含めて配下の要素数(leaf=1) int[][] G = adjB(N, A, B); int[] dp = new int[N]; int[] answer = new int[N]; for (Node node : orderFromLeaf(N, G, 0)) { int max = -1; int notParent = 1; // 1 == self for (int next : G[node.a]) { if( next == node.parent ) continue; notParent += dp[next]; max = Math.max(dp[next], max); } // parentの方向には計算していないので計算する int parent = N - notParent; max = Math.max(parent, max); dp[node.a] = notParent; answer[node.a] = max; } return answer; } static Node[] orderFromLeaf(int N, int[][] G, int root) { ArrayDeque<Node> q = new ArrayDeque<>(); Node[] ret = new Node[N]; int idx = N-1; q.add(new Node(-1, root)); while(!q.isEmpty()) { Node n = q.poll(); ret[idx--] = n; for (int next : G[n.a]) { if( next == n.parent ) continue; q.add(new Node(n.a, next)); } } return ret; } static class Node { int parent, a; public Node(int parent, int a) { this.parent = parent; this.a = a; } } static int[][] adjB(int n, int[] from, int[] to) { int[][] adj = new int[n][]; int[] cnt = new int[n]; for (int f : from) { cnt[f]++; } for (int t : to) { cnt[t]++; } for (int i = 0; i < n; i++) { adj[i] = new int[cnt[i]]; } for (int i = 0; i < from.length; i++) { adj[from[i]][--cnt[from[i]]] = to[i]; adj[to[i]][--cnt[to[i]]] = from[i]; } return adj; } @SuppressWarnings("unused") static class FastScanner { private BufferedReader reader; private StringTokenizer tokenizer; FastScanner(InputStream in) { reader = new BufferedReader(new InputStreamReader(in)); tokenizer = null; } String next() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } String nextLine() { if (tokenizer == null || !tokenizer.hasMoreTokens()) { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken("\n"); } long nextLong() { return Long.parseLong(next()); } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } long[] nextLongArray(int n) { long[] a = new long[n]; for (int i = 0; i < n; i++) a[i] = nextLong(); return a; } } }
Submission Info
Submission Time | |
---|---|
Task | C - 高橋王国の分割統治 |
User | kusomushi |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 4210 Byte |
Status | AC |
Exec Time | 307 ms |
Memory | 47000 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt |
Subtask2 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 80 ms | 20308 KB |
sample_02.txt | AC | 69 ms | 19412 KB |
subtask1_01.txt | AC | 70 ms | 19668 KB |
subtask1_02.txt | AC | 80 ms | 20436 KB |
subtask1_03.txt | AC | 79 ms | 19924 KB |
subtask1_04.txt | AC | 72 ms | 19284 KB |
subtask1_05.txt | AC | 85 ms | 20180 KB |
subtask1_06.txt | AC | 84 ms | 20180 KB |
subtask1_07.txt | AC | 83 ms | 21588 KB |
subtask1_08.txt | AC | 84 ms | 20948 KB |
subtask1_09.txt | AC | 97 ms | 21460 KB |
subtask2_01.txt | AC | 242 ms | 42612 KB |
subtask2_02.txt | AC | 256 ms | 43860 KB |
subtask2_03.txt | AC | 275 ms | 43472 KB |
subtask2_04.txt | AC | 307 ms | 41264 KB |
subtask2_05.txt | AC | 256 ms | 47000 KB |
subtask2_06.txt | AC | 239 ms | 46528 KB |
subtask2_07.txt | AC | 266 ms | 43456 KB |