oj.uz

Submission #1011112

# Submission time Handle Problem Language Result Execution time Memory
1011112 2024-06-29T20:09:08 Z Oz121 Burza (COCI16_burza) Java 11
160 / 160
 549 ms 27500 KB 
import java.io.*;
import java.util.*;
public class burza {
    public static int num; public static int k; public static HashMap<Integer, ArrayList<Integer>> tree;
    public static int[] depth; public static int[][] interval; //Interval of leaves covered by a node
    public static int count; public static HashMap<Integer, Integer> idx;
    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()); 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);
        }
 
        if (k*k>=num) System.out.println("DA");
        else System.out.println(solve());
    }
 
    public static String solve () {
        idx = new HashMap<>(); count = 0;
        depth = new int[num];
        Arrays.fill(depth, -1); depth[0] = 0;
        dfs1(0);
 
        interval = new int[num][2];
        for (int i = 0;i<num;i++) {
            interval[i][0] = Integer.MAX_VALUE; interval[i][1] = Integer.MIN_VALUE;
        }
 
        count = 0;
        for (int i = 0;i<num;i++) {
            if (depth[i]==k) {
                interval[i][0] = idx.get(i); interval[i][1] = idx.get(i);
                dfs2(i,i); count++;
            }
        }
        //System.out.println(idx);
 
 
        /*for (int i = 0;i<num;i++) {
            System.out.println(interval[i][0]+" "+interval[i][1]);
        }*/
 
        int[] dp = new int[1<<k];
        Arrays.fill(dp, -1);
 
        for (int i = 1;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;
 
                    if (interval[l][0]<=dp[prev]+1) {
                        dp[i] = Math.max(dp[i], interval[l][1]);
                    }
                }
            }
        }
 
        if (dp[(1<<k)-1]==count-1) 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;
                if (depth[next]==k) {
                    idx.put(next, count); count++;
                }
                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
                if (idx.get(child)<interval[next][0]) interval[next][0] = idx.get(child);
                if (idx.get(child)>interval[next][1]) interval[next][1] = idx.get(child);
                dfs2(next, child);
            }
        }
    }
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 23240 KB Output is correct
2 Correct 497 ms 22944 KB Output is correct
3 Correct 55 ms 26780 KB Output is correct
4 Correct 57 ms 22076 KB Output is correct
5 Correct 64 ms 22656 KB Output is correct
6 Correct 47 ms 26664 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 22616 KB Output is correct
2 Correct 449 ms 23000 KB Output is correct
3 Correct 57 ms 22420 KB Output is correct
4 Correct 53 ms 22020 KB Output is correct
5 Correct 470 ms 22784 KB Output is correct
6 Correct 70 ms 22588 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 22764 KB Output is correct
2 Correct 491 ms 22516 KB Output is correct
3 Correct 56 ms 22456 KB Output is correct
4 Correct 55 ms 26216 KB Output is correct
5 Correct 66 ms 24608 KB Output is correct
6 Correct 48 ms 22236 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 27248 KB Output is correct
2 Correct 482 ms 22520 KB Output is correct
3 Correct 55 ms 22388 KB Output is correct
4 Correct 56 ms 22436 KB Output is correct
5 Correct 61 ms 23044 KB Output is correct
6 Correct 49 ms 22168 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 27500 KB Output is correct
2 Correct 534 ms 22928 KB Output is correct
3 Correct 54 ms 22576 KB Output is correct
4 Correct 54 ms 22504 KB Output is correct
5 Correct 70 ms 23308 KB Output is correct
6 Correct 62 ms 24992 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 22708 KB Output is correct
2 Correct 499 ms 23020 KB Output is correct
3 Correct 52 ms 22508 KB Output is correct
4 Correct 53 ms 22284 KB Output is correct
5 Correct 69 ms 22504 KB Output is correct
6 Correct 60 ms 22840 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 23352 KB Output is correct
2 Correct 465 ms 23004 KB Output is correct
3 Correct 51 ms 22392 KB Output is correct
4 Correct 56 ms 24572 KB Output is correct
5 Correct 464 ms 22672 KB Output is correct
6 Correct 65 ms 22820 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 22516 KB Output is correct
2 Correct 479 ms 24676 KB Output is correct
3 Correct 50 ms 22740 KB Output is correct
4 Correct 53 ms 22812 KB Output is correct
5 Correct 61 ms 22824 KB Output is correct
6 Correct 68 ms 23072 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22868 KB Output is correct
2 Correct 549 ms 22972 KB Output is correct
3 Correct 54 ms 22616 KB Output is correct
4 Correct 54 ms 22416 KB Output is correct
5 Correct 61 ms 25068 KB Output is correct
6 Correct 68 ms 23520 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 25240 KB Output is correct
2 Correct 505 ms 22452 KB Output is correct
3 Correct 64 ms 24456 KB Output is correct
4 Correct 68 ms 24624 KB Output is correct
5 Correct 228 ms 23276 KB Output is correct
6 Correct 53 ms 22332 KB Output is correct