Submission #697090

#	Time	Username	Problem	Language	Result	Execution time	Memory
697090		nicolexxuu	Burza (COCI16_burza)	Java	160 / 160	255 ms	12788 KiB

burza

// 

import java.util.*;
import java.io.*;

public class burza {
	static ArrayList<Integer>[] adj, kNodes;
	static int[][] inv;
	static int ctr = 0;
	static int N, K;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		adj = new ArrayList[N];
		kNodes = new ArrayList[K+1];
		inv = new int[N][2];
		for(int i = 0; i < N; i++) adj[i] = new ArrayList<>();
		for(int i = 0; i <= K; i++) kNodes[i] = new ArrayList<>();
		
		for(int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken())-1, B = Integer.parseInt(st.nextToken())-1;
			adj[A].add(B);
			adj[B].add(A);
		}
		
		if(K*K >= N) System.out.println("DA");
		else {
			dfs(0, 0, -1);
			
			int[] dp = new int[1<<K]; // treat depth 1 as 0
			dp[0] = -1;
			for(int mask = 1; mask < (1 << K); mask++) {
//				System.out.println("mask: " + Integer.toBinaryString(mask));
				for(int d = 0; d < K; d++) { 
					if((mask & (1 << d)) == 0) continue;
					int prev = dp[mask - (1<<d)];
					for(int node : kNodes[d+1]) {
//						System.out.println("node: " + node + " bounds: " + inv[node][0] + " " + inv[node][1]);
						if(inv[node][0] <= prev+1) 
							dp[mask] = Math.max(dp[mask], inv[node][1]);
					}
				}
				
//				System.out.println("dp: " + dp[mask]);
			}
//			System.out.println("ctr: " + ctr);
			if(dp[(1<<K)-1] == ctr-1) System.out.println("DA");
			else System.out.println("NE");
		}
		br.close();
		
		
	}
	
	public static void dfs(int idx, int depth, int par) {
		inv[idx][0] = Integer.MAX_VALUE;
		inv[idx][1] = Integer.MIN_VALUE;
		kNodes[depth].add(idx);
		if(depth == K) {
			inv[idx][0] = inv[idx][1] = ctr++;
			return;
		}
		
		
		
		for(int to : adj[idx]) {
			if(to == par) continue;
			dfs(to, depth+1, idx);
			inv[idx][0] = Math.min(inv[idx][0], inv[to][0]);
			inv[idx][1] = Math.max(inv[idx][1], inv[to][1]);
		}
	}
}

Compilation message (stderr)

Note: burza.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16