Submission #369223

#	Time	Username	Problem	Language	Result	Execution time	Memory
369223		JerryLiu06	Bitaro’s Party (JOI18_bitaro)	Java	0 / 100	1512 ms	37240 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 run a DFS from (possibly) every node, such that we iterate over all possible
// paths. Now, we wish to find, for each node, the SQRT(N) furthest nodes from it. To do this efficiently, we update the
// furthest SQRT(N) nodes at each node on the path. This can be done in O(M log N).

// 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) + M log N). 

@SuppressWarnings("unchecked") class bitaro {

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

    static TreeSet<Node>[] far = new TreeSet[100010];
    static ArrayList<Edge>[] adj = new ArrayList[100010];
    static ArrayList<Integer>[] radj = new ArrayList[100010];

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

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

    static Stack<Node> path = new Stack<Node>();
    static boolean[] vis = new boolean[100010];

    static final int BLOCK = 320;
    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<>(); radj[i] = new ArrayList<>(); far[i] = new TreeSet<>(); 
        }
        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(new Edge(B, i)); radj[B].add(A); inDeg[A]++;
        }
        path.add(new Node(-1, -1)); for (int i = 0; i < N; i++) if (!vis[i]) DFS(i);

        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) { 
                TOP(T); for (int j = 0; j < N; j++) if (!mark[j]) {
                    ans = Math.max(ans, maxDist[j]);
                }
            } 
            else for (Node n : far[T]) if (!mark[n.node]) { ans = n.dist; break; }

            System.out.println(ans);
        }
    }
    static void TOP(int node) {
        Queue<Integer> q = new LinkedList<Integer>(); int[] deg = new int[N];
        Arrays.fill(maxDist, -1); maxDist[node] = 0;

        for (int i = 0; i < N; i++) deg[i] = inDeg[i];

        for (int i = node + 1; i < N; i++) for (int nxt : radj[i]) {
            if (nxt > node) continue;

            deg[nxt]--; if (inDeg[nxt] == 0) q.add(nxt);
        }
        while (!q.isEmpty()) { int cur = q.poll();
            for (int nxt : radj[cur]) {
                maxDist[nxt] = Math.max(maxDist[nxt], maxDist[cur] + 1);

                deg[nxt]--; if (deg[nxt] == 0) q.add(nxt);
            }
        }
    }
    static void DFS(int node) {
        path.add(new Node(node, path.peek().dist + 1)); 

        for (Node n : path) { if (n.dist == -1) continue;

            if (far[path.peek().node].size() < BLOCK) {
                far[path.peek().node].add(new Node(n.node, path.peek().dist - n.dist)); continue;
            }
            if (path.peek().dist - n.dist <= far[path.peek().node].last().dist) break;

            far[path.peek().node].add(new Node(n.node, path.peek().dist - n.dist));
            far[path.peek().node].pollLast();
        }
        for (Edge nxt : adj[node]) DFS(nxt.to); vis[path.pop().node] = true;
    }
    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) ? (node - n.node) : (n.dist - dist); 
        }
    }
    static class Edge { public int to, ind; public Edge(int a, int b) { to = a; ind = b; } }
}

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