Submission #825586

#	Time	Username	Problem	Language	Result	Execution time	Memory
825586		powervic08	Burza (COCI16_burza)	Java	0 / 160	72 ms	8800 KiB

burza

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

public class burza {

    static int[] dp;
    static ArrayList<ArrayList<Integer>> arr;

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        dp = new int[n];
        arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arr.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(f.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            arr.get(x).add(y);
            arr.get(y).add(x);
        }
        out.println(fillDp(0, new boolean[n]) < k ? "DA" : "NE");
        out.close();
        f.close();
    }

    public static int fillDp(int i, boolean[] visited) {
        visited[i] = true;
        if (dp[i] != 0) return dp[i];
        if (arr.get(i).size() == 0) return 0;
        else if (arr.get(i).size() == 1 && i != 0) return 0;
        ArrayList<Integer> pos = new ArrayList<>();
        for (int x : arr.get(i)) {
            if (!visited[x])
                pos.add(fillDp(x, visited) + 1);
        }
        Collections.sort(pos);
        if (pos.size() == 1) return 0;
        return dp[i] = pos.get(pos.size() - 2);
    }

}

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