Submission #168923

# Submission time Handle Problem Language Result Execution time Memory
168923 2019-12-17T07:34:18 Z gokuvegeta561 Dynamite (POI11_dyn) Java 11
Compilation error
0 ms 0 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 g 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 g(), "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());
		}
	}
}

Compilation message

dyn.java:9: error: class g is public, should be declared in a file named g.java
public class g implements Runnable {
       ^
1 error