Submission #1502939
Source Code Expand
import java.util.*; public class Main{ static int N; static ArrayList<Integer>[] list; static int []dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); list = new ArrayList[N]; dp = new int[N]; for(int i = 0 ;i < N;i++){ list[i] = new ArrayList<Integer>(); } for(int i = 1;i < N;i++){ int x = sc.nextInt(); list[x].add(i); } dfs(0); StringBuilder sb = new StringBuilder(); for (int i = 0; i < N; i++) { int ans = N - dp[i]; for (int item : list[i]) { ans = Math.max(ans, dp[item]); } sb.append(ans + "\n"); } System.out.print(sb); } static int dfs(int now) { int res = 1; for (int next : list[now]) { res += dfs(next); } return dp[now] = res; } }
Submission Info
Submission Time | |
---|---|
Task | C - 高橋王国の分割統治 |
User | suesue |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 1228 Byte |
Status | AC |
Exec Time | 552 ms |
Memory | 90244 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
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 | 91 ms | 21844 KB |
sample_02.txt | AC | 92 ms | 19284 KB |
subtask1_01.txt | AC | 89 ms | 21844 KB |
subtask1_02.txt | AC | 91 ms | 21332 KB |
subtask1_03.txt | AC | 98 ms | 21588 KB |
subtask1_04.txt | AC | 96 ms | 19924 KB |
subtask1_05.txt | AC | 143 ms | 20504 KB |
subtask1_06.txt | AC | 138 ms | 23084 KB |
subtask1_07.txt | AC | 138 ms | 24640 KB |
subtask1_08.txt | AC | 140 ms | 22276 KB |
subtask1_09.txt | AC | 139 ms | 25552 KB |
subtask2_01.txt | AC | 467 ms | 63504 KB |
subtask2_02.txt | AC | 504 ms | 66612 KB |
subtask2_03.txt | AC | 540 ms | 72896 KB |
subtask2_04.txt | AC | 536 ms | 70764 KB |
subtask2_05.txt | AC | 487 ms | 65352 KB |
subtask2_06.txt | AC | 466 ms | 68184 KB |
subtask2_07.txt | AC | 552 ms | 90244 KB |