Submission #366275

#	Time	Username	Problem	Language	Result	Execution time	Memory
366275		JerryLiu06	Bitaro’s Party (JOI18_bitaro)	Java	0 / 100	2045 ms	69308 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[] maxDist = new int[100010];

    static Stack<Node> path = new Stack<Node>();

    static boolean[] vis = new boolean[100010];

    static final int INF = Integer.MAX_VALUE / 3; 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);
        }
        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 >= far[T].size()) { 
                BFS(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 BFS(int node) {
        Arrays.fill(maxDist, -1); Queue<Integer> q = new LinkedList<Integer>();

        maxDist[node] = 0; q.add(node);

        while (!q.isEmpty()) { int cur = q.poll();

            for (int nxt : radj[cur]) if (maxDist[nxt] < maxDist[cur] + 1) {
                maxDist[nxt] = maxDist[cur] + 1; 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