Submission #592333

#	Time	Username	Problem	Language	Result	Execution time	Memory
592333		DylanSmith	Burza (COCI16_burza)	Java	0 / 160	81 ms	8736 KiB

burza

import java.util.*;
import java.io.*;
public class burza {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt(), K = in.nextInt();
        List<Integer>[] adj = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < N - 1; i++) {
            int u = in.nextInt() - 1, v = in.nextInt() - 1;
            adj[u].add(v);
            adj[v].add(u);
        }
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        List<Integer> sort = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            sort.add(u);
            for (int v : adj[u]) {
                adj[v].remove(adj[v].indexOf(u));
                q.offer(v);
            }
        }
        Collections.reverse(sort);
        int[] dp = new int[N];
        for (int i : sort) {
            dp[i] = adj[i].isEmpty() ? 0 : Integer.MAX_VALUE;
            for (int j : adj[i]) {
                int max = 0;
                for (int k : adj[i]) {
                    if (k == j) {
                        continue;
                    }
                    max = Math.max(max, dp[k]);
                }
                dp[i] = Math.min(dp[i], max);
            }
            dp[i] += adj[i].size() >= 2 ? 1 : 0;
        }
        out.println(dp[0] < K ? "DA" : "NE");
        
        out.close();
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

Compilation message (stderr)

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

• 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