oj.uz

Submission #873271

# Submission time Handle Problem Language Result Execution time Memory
873271 2023-11-14T17:43:40 Z bobbilyking Bosses (BOI16_bosses) Java 11
67 / 100
 1500 ms 34288 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 = 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[j] == -1) w = false;
			if (!w) continue;
		tot = 0;	
          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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22288 KB Output is correct
2 Correct 62 ms 22000 KB Output is correct
3 Correct 49 ms 22676 KB Output is correct
4 Correct 50 ms 22460 KB Output is correct
5 Correct 52 ms 26780 KB Output is correct
6 Correct 55 ms 24748 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22288 KB Output is correct
2 Correct 62 ms 22000 KB Output is correct
3 Correct 49 ms 22676 KB Output is correct
4 Correct 50 ms 22460 KB Output is correct
5 Correct 52 ms 26780 KB Output is correct
6 Correct 55 ms 24748 KB Output is correct
7 Correct 59 ms 24560 KB Output is correct
8 Correct 63 ms 23980 KB Output is correct
9 Correct 58 ms 22396 KB Output is correct
10 Correct 113 ms 25964 KB Output is correct
11 Correct 130 ms 29572 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 22288 KB Output is correct
2 Correct 62 ms 22000 KB Output is correct
3 Correct 49 ms 22676 KB Output is correct
4 Correct 50 ms 22460 KB Output is correct
5 Correct 52 ms 26780 KB Output is correct
6 Correct 55 ms 24748 KB Output is correct
7 Correct 59 ms 24560 KB Output is correct
8 Correct 63 ms 23980 KB Output is correct
9 Correct 58 ms 22396 KB Output is correct
10 Correct 113 ms 25964 KB Output is correct
11 Correct 130 ms 29572 KB Output is correct
12 Correct 277 ms 31408 KB Output is correct
13 Correct 253 ms 27320 KB Output is correct
14 Correct 1099 ms 34288 KB Output is correct
15 Correct 440 ms 32008 KB Output is correct
16 Execution timed out 1542 ms 32584 KB Time limit exceeded
17 Halted 0 ms 0 KB -