oj.uz

Submission #1010410

# Submission time Handle Problem Language Result Execution time Memory
1010410 2024-06-29T05:20:38 Z Oz121 Burza (COCI16_burza) Java 11
0 / 160
 1000 ms 44844 KB 
import java.io.*;
import java.util.*;
public class burza {
    public static int num; public static HashMap<Integer, ArrayList<Integer>> tree;
    public static int[] depth; public static HashMap<Integer, HashSet<Integer>> children;
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        num = Integer.parseInt(l1.nextToken()); int k = Integer.parseInt(l1.nextToken()); tree = new HashMap<>();

        for (int i = 0;i<num;i++) tree.put(i,new ArrayList<>());
        for (int i = 0;i<num-1;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1;
            tree.get(a).add(b); tree.get(b).add(a);
        }

        depth = new int[num];
        Arrays.fill(depth, -1); depth[0] = 0;
        dfs1(0);


        if (k*k>=num) System.out.println("NE");
        else System.out.println(solve(k));
    }

    public static String solve (int k) {
        children = new HashMap<>(); //Children at depth k
        for (int i = 0;i<num;i++) children.put(i,new HashSet<>());

        int count = 0;
        for (int i = 0;i<num;i++) {
            if (depth[i]==k) {
                children.get(i).add(i);
                dfs2(i,i); count++;
            }
        }

        //System.out.println(children);

        HashSet<Integer>[] dp = new HashSet[1<<k];
        for (int i = 0;i<1<<k;i++) dp[i] = new HashSet<>();

        for (int j = 0;j<num;j++) {
            if (depth[j]==1) dp[1] = children.get(j);
        }

        for (int i = 2;i<1<<k;i++) {
            for (int j = 0;j<k;j++) {
                if ((i&(1<<j))==0) continue;

                int prev = i-(1<<j);

                for (int l = 0;l<num;l++) {
                    if (depth[l]!=j+1) continue;
                    HashSet<Integer> temp = new HashSet<>();
                    temp.addAll(dp[prev]); temp.addAll(children.get(j));

                    if (temp.size()>dp[i].size()) dp[i] = temp;
                }
            }
        }

        if (dp[(1<<k)-1].size()>=count) return "DA";
        else return "NE";
    }

    public static void dfs1 (int curr) {
        for (int next : tree.get(curr)) {
            if (depth[next]==-1) {
                depth[next] = depth[curr]+1;
                dfs1(next);
            }
        }
    }

    public static void dfs2 (int curr, int child) {
        for (int next : tree.get(curr)) {
            if (depth[next]<depth[curr]) { //Going up the tree
                children.get(next).add(child);
                dfs2(next, child);
            }
        }
    }
}

Compilation message

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

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 37688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 44564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1031 ms 42456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 38196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 42788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1028 ms 44844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 43700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 34404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 32708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 38352 KB Time limit exceeded
2 Halted 0 ms 0 KB -