Submission #1011116

#TimeUsernameProblemLanguageResultExecution timeMemory
1011116Oz121Burza (COCI16_burza)Java
160 / 160
662 ms27348 KiB
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++; } } 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]); } } } } for (int i = 0;i<(1<<k);i++) { if (dp[i] == count - 1) return "DA"; } 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); } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...