Submission #168924

#	Time	Username	Problem	Language	Result	Execution time	Memory
168924		gokuvegeta561	Untitled (POI11_dyn)	Java	0 / 100	965 ms	65544 KiB

Main

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10