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

dyn

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());
		}
	}
}

Subtask #1

0 / 10.0

#	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	-

Subtask #2

0 / 10.0

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

Subtask #3

0 / 10.0

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

Subtask #4

0 / 10.0

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

Subtask #5

0 / 10.0

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

Subtask #6

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	792 ms	56856 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	916 ms	65536 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	762 ms	65556 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	664 ms	65536 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	730 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-