Submission #168925

# Submission time Handle Problem Language Result Execution time Memory
168925 2019-12-17T07:36:28 Z gokuvegeta561 Dynamite (POI11_dyn) Java 11
0 / 100
916 ms 65556 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 {
	
	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 dyn().run();
	}
	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());
		}
	}
}
# Verdict Execution time Memory Grader output
1 Correct 85 ms 9816 KB Output is correct
2 Correct 83 ms 9660 KB Output is correct
3 Incorrect 83 ms 9760 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 9672 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 10476 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 10876 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 30972 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 792 ms 56856 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 916 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 762 ms 65556 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 664 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 730 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -