Submission #318403

#	Time	Username	Problem	Language	Result	Execution time	Memory
318403		R3KT	Railway (BOI17_railway)	Java	8 / 100	1112 ms	97680 KiB

railway

import java.util.*;
import java.io.*;

public class railway {

	// https://open.kattis.com/problems/railway2
	
	static int n,m,k,log;
	static ArrayList<ArrayList<Edge>> g = new ArrayList<>();
	static int[][] parent;
	static int[] depth;
	static ArrayList<Integer> ans;
	static ArrayList<HashSet<Integer>> vals = new ArrayList<>();
	static ArrayList<ArrayList<Integer>> add = new ArrayList<>(), remove = new ArrayList<>();
	
	// TLE - java slow
	public static void main(String[] args) throws IOException, FileNotFoundException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		log = log(n);
		parent = new int[n][log];
		depth = new int[n];
		ans = new ArrayList<>();
		for (int i=0; i<n; i++) {
			g.add(new ArrayList<>());
			add.add(new ArrayList<>());
			vals.add(new HashSet<>());
			remove.add(new ArrayList<>());
		}
		
		for (int i=0; i<n-1; i++) {
			st = new StringTokenizer(in.readLine());
			int a = Integer.parseInt(st.nextToken())-1; 	
			int b = Integer.parseInt(st.nextToken())-1; 	
			g.get(a).add(new Edge(a, b, i));
			g.get(b).add(new Edge(b, a, i));
		}
		
		dfs(0, 0);	
		precomp();
		
		for (int i=0; i<m; i++) {
			st = new StringTokenizer(in.readLine());
			int c = Integer.parseInt(st.nextToken());
			int first = Integer.parseInt(st.nextToken())-1;
			add.get(first).add(i);
			int lca = first;
			for (int j=1; j<c; j++) {
				int cur = Integer.parseInt(st.nextToken())-1;
				lca = lca(lca, cur);
				add.get(cur).add(i);
			}
			remove.get(lca).add(i);
		}
		
		smalltolarge(0,-1);
		
		Collections.sort(ans);
		StringBuilder s = new StringBuilder();
		s.append(ans.size());
		s.append("\n");
		for (int i=0; i<ans.size(); i++) {
			if (i != 0 && ans.get(i) == ans.get(i-1)) continue;
			s.append(ans.get(i)+1);
			s.append(" ");
		}
		
		System.out.println(s);
	}
	
	public static void smalltolarge(int node, int parent) {
		int biggest = node;			// node with biggest length
		for (int i=0; i<g.get(node).size(); i++) {
			int to = g.get(node).get(i).to;
			if (to == parent) continue;
			smalltolarge(to, node);
			if (vals.get(to).size() > vals.get(biggest).size()) {
				biggest = to;
			}
		}
		
			// swap over so don't need to copy
		HashSet<Integer> c = vals.get(biggest);
		vals.set(biggest, vals.get(node));
		vals.set(node, c);
		
		for (int i=0; i<g.get(node).size(); i++) {
			int to = g.get(node).get(i).to;
			if (to == parent || to == biggest) continue;
			for (Integer a : vals.get(to)) {		// copy over
				vals.get(node).add(a);
			}
		}
		
		if (parent == -1) return;
		
		// add/remove values at node		
		for (int i=0; i<add.get(node).size(); i++) {
			vals.get(node).add(add.get(node).get(i));
		}
		for (int i=0; i<remove.get(node).size(); i++) {
			vals.get(node).remove(remove.get(node).get(i));
		}
		
		// answer queries
		if (vals.get(node).size() >= k) {
			for (int i=0; i<g.get(node).size(); i++) {
				if (g.get(node).get(i).to == parent) {
					ans.add(g.get(node).get(i).index);	
					break;
				}
			}
		}
	}
	
	static class Edge {
		int from; int to; int index;
		Edge (int a, int b, int c) {
			from = a;
			to = b;
			index = c;
		}
	}
	
	public static int lca(int u, int v) {	// lca of u and v
		if (depth[u] < depth[v]) {
			int temp = u; u = v; v = temp;	// swap u and v
		}
		// depth[u] >= depth[v];
		int diff = depth[u] - depth[v];
		for (int i=0; i<log; i++) {
			if (((1 << i) & diff) > 0) {
				u = parent[u][i];
			}
		}
		if (u == v) return u;
		for (int i=log-1; i>=0; i--) {
			if (parent[u][i] != parent[v][i]) {
				u = parent[u][i]; v = parent[v][i];
			}
		}
		return parent[u][0];
	}
	
	public static void precomp() {
		for (int i=1; i<log; i++) {
			for (int j=0; j<n; j++) {
				parent[j][i] = parent[parent[j][i-1]][i-1];
			}
		}
	}
	
	public static void dfs(int node, int p) {
		parent[node][0] = p;
		for (int i=0; i<g.get(node).size(); i++) {
			if (g.get(node).get(i).to == p) continue;
			depth[g.get(node).get(i).to] = depth[node]+1;
			dfs(g.get(node).get(i).to, node);
		}
	}
	
	public static int log(int n) {
		int x = 1;
		while ((1<<(x+1)) <= n) x++;
		return x;
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25