Submission #442764

#	Time	Username	Problem	Language	Result	Execution time	Memory
442764		bobbilyking	Bosses (BOI16_bosses)	Java	0 / 100	74 ms	8616 KiB

bosses

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class bosses{
	static List<Integer>[] adj;
	static int[] cost;
	static long tot;
	
	static void solve(int i) {
		if (cost[i] == -1) {
			cost[i] = 1;
			for (int x: adj[i]) {
				if (cost[x] == -1) {
					solve(x);
					cost[i]+=cost[x];
				}
			}
			tot+=cost[i];
		}
	}
	
	public static void main(String[] args) throws IOException {
		// br = new BufferedReader(new FileReader(".in"));
		// out = new PrintWriter(new FileWriter(".out"));
		//new Thread(null, new (), "peepee", 1<<28).start();
		
		int n =readInt();
		adj = new List[n];
		for (int i = 0; i < n; i++) adj[i] = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			int k= readInt();
			while(k-->0) {
				adj[readInt()-1].add(i);
			}
		}
		long min = Long.MAX_VALUE;
		for (int i = 0; i < n; i++) {
			tot = 0;
			cost = new int[n];
			Arrays.fill(cost, -1);
			solve(i);
			min = min(min,tot);
		}
		out.println(min);
		
		out.close();
	}
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	static StringTokenizer st = new StringTokenizer("");
	static String read() throws IOException{return st.hasMoreTokens() ? st.nextToken():(st = new StringTokenizer(br.readLine())).nextToken();}
	static int readInt() throws IOException{return Integer.parseInt(read());}
	static long readLong() throws IOException{return Long.parseLong(read());}
	static double readDouble() throws IOException{return Double.parseDouble(read());}
	
}

Compilation message (stderr)

Note: bosses.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 22
• Subtask 2: 0 / 45
• Subtask 3: 0 / 33