oj.uz

Submission #168924

# Submission time Handle Problem Language Result Execution time Memory
168924 2019-12-17T07:35:02 Z gokuvegeta561 Dynamite (POI11_dyn) Java 11
0 / 100
 965 ms 65544 KB 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

@SuppressWarnings("unchecked")
public class dyn implements Runnable {
	
	int n, m;
	boolean[] active;
	ArrayList<Integer>[] vs;
	
	boolean go(int dist) {
		int[] deg = new int[n];
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		for(int i = 0; i < n; ++i) {
			deg[i] = vs[i].size();
			if(deg[i] == 1) q.add(i);
		}
		int placed = 0;
		while(!q.isEmpty()) {
			//remove stupid leafs
			ArrayDeque<Integer> nq = new ArrayDeque<>();
			while(!q.isEmpty()) {
				int node = q.poll();
				if(!active[node]) {
					deg[node]--;
					for(int v : vs[node]) {
						if(--deg[v] == 1) {
							q.add(node);
						}
					}
				} else {
					nq.add(node);
				}
			}
			q = nq;
			int prevSize = 0;
			for(int iter = 0; iter < dist && !q.isEmpty(); ++iter) {
				prevSize = q.size();
				nq = new ArrayDeque<>();
				while(!q.isEmpty()) {
					int node = q.poll();
					deg[node]--;
					for(int v : vs[node]) {
						if(--deg[v] == 1) {
							nq.add(node);
						}
					}
				}
				q = nq;
			}
			//we have all nodes where we need to place stuff
			if(q.isEmpty()) placed += prevSize;
			placed += q.size();
			for(int iter = 0; iter <= dist && !q.isEmpty(); ++iter) {
				nq = new ArrayDeque<>();
				while(!q.isEmpty()) {
					int node = q.poll();
					deg[node]--;
					for(int v : vs[node]) {
						if(--deg[v] == 1) {
							nq.add(node);
						}
					}
				}
				q = nq;
			}
		}
		return placed <= m;
	}
	
	public void solve(FS in, PrintWriter out) {
		n = in.nextInt();
		m = in.nextInt();
		active = new boolean[n];
		vs = new ArrayList[n];
		for(int i = 0; i < n; ++i) {
			active[i] = in.nextInt() == 1;
			vs[i] = new ArrayList<>();
		}
		for(int i = 0; i < n - 1; ++i) {
			int u = in.nextInt() - 1;
			int v = in.nextInt() - 1;
			vs[u].add(v);
			vs[v].add(u);
		}
		int lo = 0, hi = n;
		while(lo <= hi) {
			int mid = lo + hi >> 1;
			boolean works = go(mid);
			if(works) hi = mid - 1;
			else lo = mid + 1;
		}
		out.println(lo);
	}
	
	public void run() {		
		FS in = new FS();
		PrintWriter out = new PrintWriter(System.out);
		solve(in, out);
		out.close();
	}
	
	public static void main(String[] args) {
		new Thread(null, new dyn(), "lmao", 1L<<28).start();
	}
	static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreElements()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) {}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9952 KB Output is correct
2 Correct 85 ms 9828 KB Output is correct
3 Incorrect 86 ms 9952 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 9876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 10504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 127 ms 10920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 369 ms 29504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 740 ms 56752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 965 ms 65544 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 716 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 706 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 732 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -