oj.uz

Submission #697090

# Submission time Handle Problem Language Result Execution time Memory
697090 2023-02-08T08:13:11 Z nicolexxuu Burza (COCI16_burza) Java 11
160 / 160
 255 ms 12788 KB 
// 

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

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

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 12220 KB Output is correct
2 Correct 255 ms 12656 KB Output is correct
3 Correct 69 ms 8416 KB Output is correct
4 Correct 68 ms 8440 KB Output is correct
5 Correct 87 ms 9884 KB Output is correct
6 Correct 65 ms 8388 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 12788 KB Output is correct
2 Correct 243 ms 12768 KB Output is correct
3 Correct 69 ms 8448 KB Output is correct
4 Correct 75 ms 8324 KB Output is correct
5 Correct 241 ms 12776 KB Output is correct
6 Correct 84 ms 8544 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 12668 KB Output is correct
2 Correct 248 ms 12696 KB Output is correct
3 Correct 68 ms 8404 KB Output is correct
4 Correct 69 ms 8496 KB Output is correct
5 Correct 88 ms 9712 KB Output is correct
6 Correct 63 ms 8324 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 12368 KB Output is correct
2 Correct 249 ms 12732 KB Output is correct
3 Correct 69 ms 8624 KB Output is correct
4 Correct 75 ms 8364 KB Output is correct
5 Correct 71 ms 8572 KB Output is correct
6 Correct 63 ms 8308 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 12568 KB Output is correct
2 Correct 250 ms 12652 KB Output is correct
3 Correct 73 ms 8512 KB Output is correct
4 Correct 68 ms 8476 KB Output is correct
5 Correct 90 ms 10080 KB Output is correct
6 Correct 72 ms 8484 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 12668 KB Output is correct
2 Correct 249 ms 12560 KB Output is correct
3 Correct 68 ms 8680 KB Output is correct
4 Correct 69 ms 8596 KB Output is correct
5 Correct 74 ms 8340 KB Output is correct
6 Correct 70 ms 8328 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 12560 KB Output is correct
2 Correct 255 ms 12408 KB Output is correct
3 Correct 68 ms 8368 KB Output is correct
4 Correct 72 ms 8360 KB Output is correct
5 Correct 255 ms 12544 KB Output is correct
6 Correct 86 ms 9736 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 12112 KB Output is correct
2 Correct 247 ms 12660 KB Output is correct
3 Correct 72 ms 8492 KB Output is correct
4 Correct 85 ms 8384 KB Output is correct
5 Correct 68 ms 8372 KB Output is correct
6 Correct 80 ms 8612 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12036 KB Output is correct
2 Correct 248 ms 12656 KB Output is correct
3 Correct 75 ms 8408 KB Output is correct
4 Correct 75 ms 8536 KB Output is correct
5 Correct 69 ms 8472 KB Output is correct
6 Correct 94 ms 9752 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 12404 KB Output is correct
2 Correct 244 ms 12536 KB Output is correct
3 Correct 77 ms 8484 KB Output is correct
4 Correct 76 ms 8524 KB Output is correct
5 Correct 172 ms 12200 KB Output is correct
6 Correct 70 ms 8220 KB Output is correct