Submission #433506

#	Time	Username	Problem	Language	Result	Execution time	Memory
433506		basher199	Burza (COCI16_burza)	Java	0 / 160	1014 ms	81200 KiB

burza

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


public class burza {
    Map<Integer, List<Integer>> edges = new HashMap<>();
    List<Integer> values = new ArrayList<>();

    int n;
    int k;
    int[] left;
    int[] right;
    int[] depth;

    int i = 0;

    public static void main(String[] args) throws IOException {
        burza b = new burza();
        b.solve();
    }

    public void solve() throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(f.readLine());

        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        if (k * k + 1 >= n) {
            System.out.println("DA");
            return;
        }

        left = new int[n + 1];
        right = new int[n + 1];
        depth = new int[n + 1];
        depth[0] = -1;
        List<Integer> temp = new ArrayList<>();
        temp.add(1);
        edges.put(0, temp);

        for (int i = 0; i < n; i++) {
            edges.put(i, new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(f.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;

            edges.get(a).add(b);
            edges.get(b).add(a);

        }
        dfs(0, -1);

        /*
         * for (int i = 0; i < values.size(); i++) { System.out.println(values.get(i));
         * }
         */
        boolean[][] dp = new boolean[n][(1 << k)]; // calculates whether the first j leaves of the depth j can be covered by
                                            // the nodes of depth in mask

        boolean[][] state = new boolean[(1 << k)][2];

        values.remove(values.size() - 1);
        for (int t : values) {
            for (int j = 0; j < (1 << k); j++) {
           //     System.out.println(dp.length + " " + left[t] + " " + dp[2].length);
                // if (left[t] > 0 && dp[left[t] - 1][j] && (j & (1 << depth[t])) == 0) { //
                if (left[t] > 0 && dp[left[t] - 1][j] && (j & (1 << depth[t])) == 0) { //
                    // essentially the leaves before this and then whether this counts
                    state[j ^ (1 << depth[t])][1] = true;
                }
                if (depth[t] < k && state[j][0])
                    state[j][1] = true;
            }
            if (left[t] == 0) {
                state[1 << depth[t]][1] = true;
            }
            for (int j = 0; j < state.length; j++) {
                state[j][0] = state[j][1];
            }
            for (int i = 0; i < dp[0].length; i++) {
                dp[right[t]][i] = state[i][0];
            }
        }
        for (i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                if(dp[i][j]) {
                    System.out.println("DA");
                    return;
                }
            }
        }
        System.out.println("NE");
    }

    private void dfs(int cur, int prev) {
        left[cur] = i;
        if (depth[cur] < k - 1) {
            for (int m : edges.get(cur)) {
                if (m != prev) {
                    depth[m] = depth[cur] + 1;
                    dfs(m, cur);
                }
            }

        }
        i++;
        right[cur] = i;
        values.add(cur);

    }
}

• 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