# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
873270 | bobbilyking | Bosses (BOI16_bosses) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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); cost[h] = 1;
for (int j = 0; j < n; j++) nadj[j] = new ArrayList<Integer>();
while (!q.isEmpty()) {
int h = q.poll();
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());}
}