Submission #1263017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263017		vampirr	Bosses (BOI16_bosses)	Java	100 / 100	1198 ms	157084 KiB

bosses

import java.util.*;
public class bosses {
	
	static int N;
	static ArrayList<Integer>[] adjlist;
	static int cost,nodesvisited;
	static int[] depth;
	
	public static void bfs(int start) {
		depth = new int[N+1];
		depth[start]=1;
		Deque<Integer> q = new ArrayDeque<Integer>();
		q.add(start);
		cost=1;
		while (!q.isEmpty()) {
			nodesvisited++;
			int curr = q.poll();
			for (int other : adjlist[curr]) {
				if (depth[other]==0) {
					depth[other]=depth[curr]+1;
					cost+=depth[other];
					q.add(other);
				}
			}
		}
		
	}
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		adjlist = new ArrayList[N+1];
		for (int i=0; i<=N; i++) {
			adjlist[i]=new ArrayList<Integer>();
		}
		for (int i=1; i<=N; i++) {
			int k = in.nextInt();
			while (k-->0) {
				int a = in.nextInt();
				adjlist[a].add(i);
			}
		}
		in.close();
		int ans=Integer.MAX_VALUE;
		for (int i=1; i<=N; i++) {
			nodesvisited=0;
			bfs(i);
			if(nodesvisited == N) {
				ans = Math.min(cost, ans);
			}
		}
		System.out.println(ans);

	}

}

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