Submission #1010410

#TimeUsernameProblemLanguageResultExecution timeMemory
1010410Oz121Burza (COCI16_burza)Java
0 / 160
1076 ms44844 KiB
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 (stderr)

Note: burza.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#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...