oj.uz

Submission #519299

# Submission time Handle Problem Language Result Execution time Memory
519299 2022-01-26T07:30:40 Z derrick20 Bitaro’s Party (JOI18_bitaro) Java 11
7 / 100
 1447 ms 524292 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 = (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

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 68 ms 8944 KB Output is correct
2 Correct 73 ms 9028 KB Output is correct
3 Correct 85 ms 8928 KB Output is correct
4 Correct 79 ms 8972 KB Output is correct
5 Correct 245 ms 17956 KB Output is correct
6 Correct 269 ms 17940 KB Output is correct
7 Correct 261 ms 15900 KB Output is correct
8 Correct 378 ms 26376 KB Output is correct
9 Correct 386 ms 26556 KB Output is correct
10 Correct 380 ms 26276 KB Output is correct
11 Correct 763 ms 23976 KB Output is correct
12 Correct 837 ms 20836 KB Output is correct
13 Correct 813 ms 23812 KB Output is correct
14 Correct 726 ms 22944 KB Output is correct
15 Correct 928 ms 19828 KB Output is correct
16 Correct 705 ms 22500 KB Output is correct
17 Correct 753 ms 22492 KB Output is correct
18 Correct 658 ms 19880 KB Output is correct
19 Correct 801 ms 23256 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8944 KB Output is correct
2 Correct 73 ms 9028 KB Output is correct
3 Correct 85 ms 8928 KB Output is correct
4 Correct 79 ms 8972 KB Output is correct
5 Correct 245 ms 17956 KB Output is correct
6 Correct 269 ms 17940 KB Output is correct
7 Correct 261 ms 15900 KB Output is correct
8 Correct 378 ms 26376 KB Output is correct
9 Correct 386 ms 26556 KB Output is correct
10 Correct 380 ms 26276 KB Output is correct
11 Correct 763 ms 23976 KB Output is correct
12 Correct 837 ms 20836 KB Output is correct
13 Correct 813 ms 23812 KB Output is correct
14 Correct 726 ms 22944 KB Output is correct
15 Correct 928 ms 19828 KB Output is correct
16 Correct 705 ms 22500 KB Output is correct
17 Correct 753 ms 22492 KB Output is correct
18 Correct 658 ms 19880 KB Output is correct
19 Correct 801 ms 23256 KB Output is correct
20 Correct 1447 ms 32620 KB Output is correct
21 Correct 746 ms 31540 KB Output is correct
22 Correct 1389 ms 34476 KB Output is correct
23 Correct 1330 ms 33892 KB Output is correct
24 Runtime error 1024 ms 524292 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8944 KB Output is correct
2 Correct 73 ms 9028 KB Output is correct
3 Correct 85 ms 8928 KB Output is correct
4 Correct 79 ms 8972 KB Output is correct
5 Correct 245 ms 17956 KB Output is correct
6 Correct 269 ms 17940 KB Output is correct
7 Correct 261 ms 15900 KB Output is correct
8 Correct 378 ms 26376 KB Output is correct
9 Correct 386 ms 26556 KB Output is correct
10 Correct 380 ms 26276 KB Output is correct
11 Correct 763 ms 23976 KB Output is correct
12 Correct 837 ms 20836 KB Output is correct
13 Correct 813 ms 23812 KB Output is correct
14 Correct 726 ms 22944 KB Output is correct
15 Correct 928 ms 19828 KB Output is correct
16 Correct 705 ms 22500 KB Output is correct
17 Correct 753 ms 22492 KB Output is correct
18 Correct 658 ms 19880 KB Output is correct
19 Correct 801 ms 23256 KB Output is correct
20 Correct 1447 ms 32620 KB Output is correct
21 Correct 746 ms 31540 KB Output is correct
22 Correct 1389 ms 34476 KB Output is correct
23 Correct 1330 ms 33892 KB Output is correct
24 Runtime error 1024 ms 524292 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -