oj.uz

Submission #519285

# Submission time Handle Problem Language Result Execution time Memory
519285 2022-01-26T07:14:10 Z derrick20 Bitaro’s Party (JOI18_bitaro) Java 11
7 / 100
 2000 ms 87476 KB 
/**
 * 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 = N + 1; // (int) sqrt(N) / 3;
        dpPaths = new int[N][sqrtN][2];
        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][0] == 0) break;
                    if (!busy[dpPaths[partyHost][i][1]]) {
                        ans = dpPaths[partyHost][i][0];
                        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 int[][][] 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 boolean[] seen;
    static int[] seenSet;
    static int[] maxPath;
    static void solve(int node) {
        int deg = adjList[node].size();
        if (deg == 0) return;
        HashMap<Integer, Integer> paths = new HashMap<>();
        int seenSize = 0;
        for (int adj : adjList[node]) {
            if (!vis[adj]) {
                vis[adj] = true;
                solve(adj);
            }
            if (!seen[adj]) {
                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--) {
                int dist = dpPaths[adj][i][0];
                int dest = dpPaths[adj][i][1];
                if (dist == 0) break;
                if (!seen[dest]) {
                    seen[dest] = true;
                    seenSet[seenSize++] = dest;
                }
                maxPath[dest] = max(dist + 1, maxPath[dest]);
//                paths.merge(dpPaths[adj][i][1], dpPaths[adj][i][0] + 1, Integer::max);
            }
        }
        int[][] collectedPaths = new int[deg * sqrtN + deg][2];
        int ptr = 0;
        for (int i = 0; i < seenSize; i++) {
            int dest = seenSet[i];
            collectedPaths[ptr++] = new int[]{maxPath[dest], dest};
            seen[dest] = false;
            maxPath[dest] = 0;
        }
        Arrays.sort(collectedPaths, Comparator.comparingInt(path -> path[0]));
        System.arraycopy(collectedPaths, collectedPaths.length - sqrtN, dpPaths[node], 0, sqrtN);
    }

    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

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8900 KB Output is correct
2 Correct 65 ms 8924 KB Output is correct
3 Correct 71 ms 9020 KB Output is correct
4 Correct 91 ms 9012 KB Output is correct
5 Correct 652 ms 77780 KB Output is correct
6 Correct 704 ms 78348 KB Output is correct
7 Correct 640 ms 77284 KB Output is correct
8 Correct 637 ms 81856 KB Output is correct
9 Correct 648 ms 81772 KB Output is correct
10 Correct 641 ms 82088 KB Output is correct
11 Correct 1020 ms 85784 KB Output is correct
12 Correct 1002 ms 81320 KB Output is correct
13 Correct 1080 ms 85120 KB Output is correct
14 Correct 1057 ms 81788 KB Output is correct
15 Correct 1130 ms 79904 KB Output is correct
16 Correct 1113 ms 82984 KB Output is correct
17 Correct 1132 ms 84032 KB Output is correct
18 Correct 997 ms 78756 KB Output is correct
19 Correct 1041 ms 83008 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8900 KB Output is correct
2 Correct 65 ms 8924 KB Output is correct
3 Correct 71 ms 9020 KB Output is correct
4 Correct 91 ms 9012 KB Output is correct
5 Correct 652 ms 77780 KB Output is correct
6 Correct 704 ms 78348 KB Output is correct
7 Correct 640 ms 77284 KB Output is correct
8 Correct 637 ms 81856 KB Output is correct
9 Correct 648 ms 81772 KB Output is correct
10 Correct 641 ms 82088 KB Output is correct
11 Correct 1020 ms 85784 KB Output is correct
12 Correct 1002 ms 81320 KB Output is correct
13 Correct 1080 ms 85120 KB Output is correct
14 Correct 1057 ms 81788 KB Output is correct
15 Correct 1130 ms 79904 KB Output is correct
16 Correct 1113 ms 82984 KB Output is correct
17 Correct 1132 ms 84032 KB Output is correct
18 Correct 997 ms 78756 KB Output is correct
19 Correct 1041 ms 83008 KB Output is correct
20 Execution timed out 2094 ms 87476 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8900 KB Output is correct
2 Correct 65 ms 8924 KB Output is correct
3 Correct 71 ms 9020 KB Output is correct
4 Correct 91 ms 9012 KB Output is correct
5 Correct 652 ms 77780 KB Output is correct
6 Correct 704 ms 78348 KB Output is correct
7 Correct 640 ms 77284 KB Output is correct
8 Correct 637 ms 81856 KB Output is correct
9 Correct 648 ms 81772 KB Output is correct
10 Correct 641 ms 82088 KB Output is correct
11 Correct 1020 ms 85784 KB Output is correct
12 Correct 1002 ms 81320 KB Output is correct
13 Correct 1080 ms 85120 KB Output is correct
14 Correct 1057 ms 81788 KB Output is correct
15 Correct 1130 ms 79904 KB Output is correct
16 Correct 1113 ms 82984 KB Output is correct
17 Correct 1132 ms 84032 KB Output is correct
18 Correct 997 ms 78756 KB Output is correct
19 Correct 1041 ms 83008 KB Output is correct
20 Execution timed out 2094 ms 87476 KB Time limit exceeded
21 Halted 0 ms 0 KB -