oj.uz

Submission #697086

# Submission time Handle Problem Language Result Execution time Memory
697086 2023-02-08T08:09:22 Z nicolexxuu Burza (COCI16_burza) Java 11
160 / 160
 281 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 depth 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;
		if(depth > K) return;
		if(depth == K) inv[idx][0] = inv[idx][1] = ctr++;
		
		kNodes[depth].add(idx);
		
		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 117 ms 12128 KB Output is correct
2 Correct 261 ms 12548 KB Output is correct
3 Correct 75 ms 8360 KB Output is correct
4 Correct 71 ms 8464 KB Output is correct
5 Correct 90 ms 9812 KB Output is correct
6 Correct 62 ms 8384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 12396 KB Output is correct
2 Correct 251 ms 12612 KB Output is correct
3 Correct 69 ms 8456 KB Output is correct
4 Correct 79 ms 8488 KB Output is correct
5 Correct 246 ms 12640 KB Output is correct
6 Correct 81 ms 8444 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 12704 KB Output is correct
2 Correct 257 ms 12556 KB Output is correct
3 Correct 66 ms 8464 KB Output is correct
4 Correct 69 ms 8580 KB Output is correct
5 Correct 91 ms 9648 KB Output is correct
6 Correct 59 ms 8384 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 12344 KB Output is correct
2 Correct 248 ms 12720 KB Output is correct
3 Correct 69 ms 8684 KB Output is correct
4 Correct 80 ms 8440 KB Output is correct
5 Correct 72 ms 8444 KB Output is correct
6 Correct 65 ms 8228 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 12788 KB Output is correct
2 Correct 253 ms 12532 KB Output is correct
3 Correct 77 ms 8508 KB Output is correct
4 Correct 73 ms 8360 KB Output is correct
5 Correct 93 ms 9744 KB Output is correct
6 Correct 71 ms 8404 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 12512 KB Output is correct
2 Correct 281 ms 12452 KB Output is correct
3 Correct 70 ms 8464 KB Output is correct
4 Correct 71 ms 8304 KB Output is correct
5 Correct 75 ms 8352 KB Output is correct
6 Correct 72 ms 8300 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 12604 KB Output is correct
2 Correct 242 ms 12656 KB Output is correct
3 Correct 74 ms 8508 KB Output is correct
4 Correct 73 ms 8612 KB Output is correct
5 Correct 243 ms 12644 KB Output is correct
6 Correct 91 ms 9668 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 12052 KB Output is correct
2 Correct 255 ms 12560 KB Output is correct
3 Correct 71 ms 8412 KB Output is correct
4 Correct 73 ms 8652 KB Output is correct
5 Correct 69 ms 8424 KB Output is correct
6 Correct 84 ms 8568 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12168 KB Output is correct
2 Correct 275 ms 12500 KB Output is correct
3 Correct 70 ms 8384 KB Output is correct
4 Correct 68 ms 8536 KB Output is correct
5 Correct 72 ms 8352 KB Output is correct
6 Correct 89 ms 9888 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 12224 KB Output is correct
2 Correct 267 ms 12536 KB Output is correct
3 Correct 70 ms 8636 KB Output is correct
4 Correct 71 ms 8360 KB Output is correct
5 Correct 165 ms 12308 KB Output is correct
6 Correct 65 ms 8532 KB Output is correct