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
AC × 2
AC × 11
AC × 18
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