Submission #382632

#	Time	Username	Problem	Language	Result	Execution time	Memory
382632		vijay	Triumphal arch (POI13_luk)	Java	60 / 100	2094 ms	65768 KiB

luk

import java.io.*;
import java.util.*;

public class luk {
    static int N;
    static ArrayList<Integer>[] adj;
    public static void main(String[] args) throws IOException, FileNotFoundException {
        Scanner in = new Scanner(System.in);
        // Scanner in = new Scanner(new File("luk.in"));
        // PrintWriter out = new PrintWriter("luk.out");

        N = in.nextInt();
        adj = new ArrayList[N];

        for(int i = 0; i < N; i++){
            adj[i] = new ArrayList<>(); 
        }

        for(int i = 0; i < N - 1; i++){
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            adj[a].add(b);
            adj[b].add(a);
        }

        int a = 1;
        int b = N;
        while(a != b){
            int mid = (a + b)/2;
            if(recurse(0, -1, mid) <= 0){
                b = mid;
            } else {
                a = mid + 1;
            }
        }

        System.out.println(a);
    }

    static int recurse(int position, int prev, int crew){
        int j = 0;
        for(int ap: adj[position]){
            if(ap != prev){
                j += recurse(ap, position, crew) + 1;
            }
        }
        return Math.max(0, j - crew);
    }
}

Compilation message (stderr)

Note: luk.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10