oj.uz

Submission #442764

# Submission time Handle Problem Language Result Execution time Memory
442764 2021-07-09T00:33:26 Z bobbilyking Bosses (BOI16_bosses) Java 11
0 / 100
 74 ms 8616 KB 
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

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

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8616 KB Output is correct
2 Incorrect 70 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8616 KB Output is correct
2 Incorrect 70 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8616 KB Output is correct
2 Incorrect 70 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -