Submission #442765

#	Time	Username	Problem	Language	Result	Execution time	Memory
442765		bobbilyking	Bosses (BOI16_bosses)	Java	0 / 100	71 ms	8364 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 = 0;
	static long solve(int i) {
		long cost = 1;
		for (int x: nadj[i]) cost += solve(x);
		tot+=cost;
		return cost;
	}
	
	static List<Integer>[] nadj;
	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];
		nadj = 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++) {
			cost = new int[n];
			Arrays.fill(cost, -1);
			Queue<Integer> q = new ArrayDeque<Integer>();
			q.add(i);
			for (int j = 0; j < n; j++) nadj[j] = new ArrayList<Integer>();
			while (!q.isEmpty()) {
				int h = q.poll();
				cost[h] = 1;
				for (int x: adj[h]) {
					if (cost[x] == -1) {
						q.add(x);
						nadj[h].add(x);
						cost[x]=1;
					}
				}
			}
			boolean w= true;
			for (int j =0 ; j < n; j++) if (cost[i] == -1) w = false;
			if (!w) continue;
			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