Submission #364322

#	Time	Username	Problem	Language	Result	Execution time	Memory
364322		JerryLiu06	Bitaro’s Party (JOI18_bitaro)	Java	0 / 100	320 ms	21092 KiB

bitaro

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

// Solution Notes: The key constraint that we must notice is that Y_1 + Y_2 + ... + Y_Q <= N. This motivates us to find 
// a solution using SQRT Decomposition. We first run a Topological Sort from node 1 and calculate the maximum distance 
// of each node from node 1. Denote by dist[i][j] the maximum distance from node i to node j. Note that dist[i][j] = 
// dist[1][j] - dist[1][i], and hence can be calculated in O(1) time. The Topogical Sort can be done in O(M + N) time.

// Now, we wish to find, for each node, the SQRT(N) furthest nodes from it. To do this efficiently, we sort the nodes
// by their distance from node 1 and run through the first SQRT(N) nodes at each pass. The sort is done in O(N log(N))
// and the processing takes O(N SQRT(N)) time. Consider the case when Y_i >= SQRT(N). Note that there are at most SQRT(N)
// of these queries, and for each one we can naively loop through the nodes in O(N) time. If Y_i <= SQRT(N), then there
// must exist at least one of the furthest SQRT(N) nodes from the node in query that is not busy, so we can loop through
// these furthest nodes and calculate the maximum in O(SQRT(N)). Thus, our final time complexity is O((Q + N) SQRT(N)). 

@SuppressWarnings("unchecked") class bitaro {

    static int N, M, Q, num = 0;

    static int[] dist = new int[100010];
    static int[] comp = new int[100010];

    static ArrayList<Node>[] nDist = new ArrayList[100010];
    static ArrayList<Node>[] far = new ArrayList[100010];

    static ArrayList<Integer>[] adj = new ArrayList[100010];

    static int[] inDeg = new int[100010];

    static final int INF = Integer.MAX_VALUE / 3;
    static final int BLOCK = 315;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        for (int i = 0; i < N; i++) {
            adj[i] = new ArrayList<>(); nDist[i] = new ArrayList<>(); far[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken()) - 1;
            int B = Integer.parseInt(st.nextToken()) - 1;

            adj[A].add(B); inDeg[B]++;
        }
        genDist(); for (int i = 0; i < num; i++) Collections.sort(nDist[i]);

        for (int i = 0; i < num; i++) for (int j = 0; j < nDist[i].size(); j++) {

            for (int k = 0; k <= j && k < BLOCK; k++) {
                far[nDist[i].get(j).node].add(new Node(nDist[i].get(k).node, nDist[i].get(k).dist));
            }
        }
        for (int i = 0; i < Q; i++) { st = new StringTokenizer(br.readLine());
            int T = Integer.parseInt(st.nextToken()) - 1;
            int Y = Integer.parseInt(st.nextToken());

            int ans = -1; boolean[] mark = new boolean[N];
            
            for (int j = 0; j < Y; j++) mark[Integer.parseInt(st.nextToken()) - 1] = true;

            if (Y >= BLOCK) for (int j = 0; j < N; j++) {
                if (comp[T] != comp[j] || dist[T] < dist[j] || mark[j]) continue;

                ans = Math.max(ans, dist[T] - dist[j]);
            }
            else for (Node n : far[T]) {
                if (!mark[n.node]) { ans = dist[T] - dist[n.node]; break; }
            }
            System.out.println(ans);
        }
    }
    static void genDist() {
        Arrays.fill(dist, -INF); Queue<Integer> q = new LinkedList<Integer>(); 
        
        for (int i = 0; i < N; i++) if (inDeg[i] == 0) {
            q.add(i); dist[i] = 0; comp[i] = num++;
        }
        while (!q.isEmpty()) { int cur = q.poll();

            for (int nxt : adj[cur]) { inDeg[nxt]--;
                dist[nxt] = Math.max(dist[nxt], dist[cur] + 1);

                if (inDeg[nxt] == 0) { q.add(nxt); comp[nxt] = comp[cur]; }
            }
        }
        for (int i = 0; i < N; i++) nDist[comp[i]].add(new Node(i, dist[i]));
    }
    static class Node implements Comparable<Node> {
        public int node, dist;

        public Node(int a, int b) { node = a; dist = b; }

        public int compareTo(Node n) { return dist - n.dist; }
    }
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86