oj.uz

Submission #825587

# Submission time Handle Problem Language Result Execution time Memory
825587 2023-08-15T05:09:56 Z powervic08 Burza (COCI16_burza) Java 11
0 / 160
 73 ms 8916 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8704 KB Output is correct
2 Correct 66 ms 8628 KB Output is correct
3 Incorrect 60 ms 8736 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8672 KB Output is correct
2 Correct 60 ms 8568 KB Output is correct
3 Incorrect 60 ms 8492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8816 KB Output is correct
2 Correct 73 ms 8604 KB Output is correct
3 Incorrect 60 ms 8620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 8288 KB Output is correct
2 Correct 65 ms 8296 KB Output is correct
3 Incorrect 61 ms 8464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8488 KB Output is correct
2 Correct 59 ms 8632 KB Output is correct
3 Incorrect 61 ms 8476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8588 KB Output is correct
2 Correct 60 ms 8336 KB Output is correct
3 Incorrect 60 ms 8520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8916 KB Output is correct
2 Correct 63 ms 8696 KB Output is correct
3 Incorrect 60 ms 8468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 8648 KB Output is correct
2 Correct 64 ms 8380 KB Output is correct
3 Incorrect 61 ms 8660 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8488 KB Output is correct
2 Correct 63 ms 8676 KB Output is correct
3 Incorrect 59 ms 8612 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8684 KB Output is correct
2 Correct 65 ms 8564 KB Output is correct
3 Incorrect 62 ms 8520 KB Output isn't correct
4 Halted 0 ms 0 KB -