| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 592333 | 2022-07-08T23:59:43 Z | DylanSmith | Burza (COCI16_burza) | Java 11 | 81 ms | 8736 KB |
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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 67 ms | 8736 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 73 ms | 8276 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 65 ms | 8384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 69 ms | 8292 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 63 ms | 8480 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 81 ms | 8356 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 69 ms | 8432 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 68 ms | 8340 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 71 ms | 8428 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 68 ms | 8260 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |