Submission #1103513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103513		secretwood01	Bosses (BOI16_bosses)	Java	0 / 100	56 ms	14156 KiB

bosses

import java.util.*;
import java.io.*;

public class bosses {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int N = Integer.parseInt(br.readLine());
        Node [] Nodes = new Node[N];
        for (int i=0;i<N;i++) {
            Nodes[i] = new Node(i+1);
        }
        StringTokenizer st;
        for (int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            for (int j=0;j<num;j++) {
                int x = Integer.parseInt(st.nextToken());
                Nodes[x-1].subemps.add(i+1);
            }
        }
        int [] Freq;
        int mintotSal = Integer.MAX_VALUE;
        for (int i=0;i<N;i++) {
            int ans = 0;
            Node root = Nodes[i];
            int maxdist = 0;
            Freq = new int [N];
            if (i!=0) reset(Nodes);
            Queue<Integer> q = new LinkedList<Integer>();
            root.dist = 0;
            root.visited = true;
            q.add(i+1);
            while (q.size()>0) {
                Node curr = Nodes[q.poll()-1];
                Freq[curr.dist]++;
                maxdist = Math.max(maxdist, curr.dist);
                for (int z : curr.subemps) {
                    if (!Nodes[z-1].visited) {
                        q.add(z);
                        Nodes[z-1].visited = true;
                        Nodes[z-1].dist = curr.dist+1;
                    }
                }
            }
            for (int j=0;j<=maxdist;j++) {
                ans+=Freq[j]*(maxdist-j+1);
            }
            mintotSal = Math.min(mintotSal, ans);
        }
        pw.println(mintotSal);
        pw.close();
        br.close();
    }
    public static void reset(Node [] N) {
        for (Node x : N) {x.visited = false;x.dist = 0;}
    }
}
class Node {
    int num;
    int dist;
    ArrayList<Integer> subemps;
    boolean visited;
    public Node(int x) {
        this.num = x;
        this.subemps = new ArrayList<Integer>();
        this.visited = false;
    }
}

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