Submission #519299

#	Time	Username	Problem	Language	Result	Execution time	Memory
519299		derrick20	Bitaro’s Party (JOI18_bitaro)	Java	7 / 100	1447 ms	524292 KiB

bitaro

/**
 * author: derrick20
 * created: 1/25/22 9:47 PM
 */

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

import static java.lang.Math.*;

public class bitaro {
    static FastScanner sc = new FastScanner();
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int N = sc.nextInt(), M = sc.nextInt(), Q = sc.nextInt();
        adjList = new ArrayDeque[N];
        Arrays.setAll(adjList, i -> new ArrayDeque<>());
        for (int i = 0; i < M; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            adjList[v].add(u);
        }
        sqrtN = (int) pow(N, 0.9);
        dpPaths = new Pair[N][sqrtN];
        vis = new boolean[N];

        seen = new boolean[N];
        seenSet = new int[N];
        maxPath = new int[N];
        for (int u = 0; u < N; u++) {
            if (!vis[u]) {
                vis[u] = true;
                solve(u);
            }
        }
        boolean[] busy = new boolean[N];
        while (Q-->0) {
            int partyHost = sc.nextInt() - 1;
            int busyCount = sc.nextInt();
            int[] busyBeavers = new int[busyCount];
            Arrays.setAll(busyBeavers, i -> sc.nextInt() - 1);
            for (int beaver : busyBeavers) {
                busy[beaver] = true;
            }
            int ans = -1;
            if (busyCount < sqrtN) {
                for (int i = sqrtN - 1; i >= 0; i--) {
                    if (dpPaths[partyHost][i] == null) break;
                    if (!busy[dpPaths[partyHost][i].dest]) {
                        ans = dpPaths[partyHost][i].dist;
                        break;
                    }
                }
                if (ans == -1 && !busy[partyHost]) {
                    ans = 0;
                }
            } else {
                dpLarge = new int[N];
                Arrays.fill(dpLarge, -1);
                solveLarge(partyHost, busy);
                ans = dpLarge[partyHost];
            }
            out.println(ans);
            for (int beaver : busyBeavers) {
                busy[beaver] = false;
            }
        }
        out.close();
    }

    static ArrayDeque<Integer>[] adjList;
    static int sqrtN;
    static Pair[][] dpPaths;
    static boolean[] vis;
    static int[] dpLarge;

    static void solveLarge(int node, boolean[] busy) {
        if (!busy[node]) {
            dpLarge[node] = 0;
        }
        for (int adj : adjList[node]) {
            solveLarge(adj, busy);
            if (dpLarge[adj] != -1)
                dpLarge[node] = max(dpLarge[node], 1 + dpLarge[adj]);
        }
    }

    static class Pair {
        int dist, dest;
        public Pair(int distance, int destination) {
            dist = distance; dest = destination;
        }
    }

    static boolean[] seen;
    static int[] seenSet;
    static int[] maxPath;
    static void solve(int node) {
        int deg = adjList[node].size();
        if (deg == 0) return;
        int seenSize = 0;
        for (int adj : adjList[node]) {
            if (!vis[adj]) {
                vis[adj] = true;
                solve(adj);
            }
            if (!seen[adj]) {
                // KEY BUG FORGOT TO SET AS VISITED
                seen[adj] = true;
                seenSet[seenSize++] = adj;
            }
            maxPath[adj] = max(1, maxPath[adj]);
//            paths.merge(adj, 1, Integer::max);
            for (int i = sqrtN - 1; i >= 0; i--) {
                if (dpPaths[adj][i] == null) break;
                int dist = dpPaths[adj][i].dist;
                int dest = dpPaths[adj][i].dest;
                if (!seen[dest]) {
                    seen[dest] = true;
                    seenSet[seenSize++] = dest;
                }
                maxPath[dest] = max(dist + 1, maxPath[dest]);
//                paths.merge(dpPaths[adj][i].dest, dpPaths[adj][i].dist + 1, Integer::max);
            }
        }
        Pair[] collectedPaths = new Pair[seenSize];
        for (int i = 0; i < seenSize; i++) {
            int dest = seenSet[i];
            collectedPaths[i] = new Pair(maxPath[dest], dest);
            seen[dest] = false;
            maxPath[dest] = 0;
        }
        Arrays.sort(collectedPaths, Comparator.comparingInt(path -> path.dist));
        int start = max(0, collectedPaths.length - sqrtN);
        int length = collectedPaths.length - start;
        System.arraycopy(collectedPaths, start, dpPaths[node], sqrtN - length, length);
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        int nextInt() {
            return (int) nextLong();
        }

        long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        double nextDouble() {
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            double cur = nextLong();
            if (c != '.') {
                return neg ? -cur : cur;
            } else {
                double frac = nextLong() / cnt;
                return neg ? -cur - frac : cur + frac;
            }
        }

        String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }

    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }

    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}

Compilation message (stderr)

Note: bitaro.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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