Submission #254799

#	Time	Username	Problem	Language	Result	Execution time	Memory
254799		model_code	Viruses (BOI20_viruses)	Java	100 / 100	641 ms	41508 KiB

Viruses

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

public class Viruses {

    private static class Val implements Comparable<Val> {

        private final long value;
        private final int i;
        private final int st;
        private final int en;

        public Val(long value, int i, int st, int en) {
            this.value = value;
            this.i = i;
            this.st = st;
            this.en = en;
        }

        @Override
        public int compareTo(Val o) {
            if (this.value < o.value) {
                return -1;
            } else if (this.value > o.value) {
                return 1;
            } else {
                if (this.i < o.i) {
                    return -1;
                } else if (this.i > o.i) {
                    return 1;
                } else {
                    if (this.st < o.st) {
                        return -1;
                    } else if (this.st > o.st) {
                        return 1;
                    } else {
                        if (this.en < o.en) {
                            return -1;
                        } else if (this.en > o.en) {
                            return 1;
                        } else {
                            return 0;
                        }
                    }
                }
            }
        }
    }

    private static class Mutation {

        private final int st;
        private final int en1;
        private final Integer en2;

        public Mutation(int st, int en1) {
            this.st = st;
            this.en1 = en1;
            this.en2 = null;
        }

        public Mutation(int st, int en1, int en2) {
            this.st = st;
            this.en1 = en1;
            this.en2 = en2;
        }
    }

    private static final int MAXG = 305;
    private static final int MAXL = 55;
    private static final long MYINFLL = 1000000000000000000L;

    private static long[] a = new long[MAXG * MAXL * MAXL + 1];

    private static void set(int i, int st, int en, long val) {
        a[MAXL * MAXL * i + MAXL * st + en] = val;
    }

    private static long get(int i, int st, int en) {
        return a[MAXL * MAXL * i + MAXL * st + en];
    }

    private static TreeSet<Val> q = new TreeSet<>();

    private static void update(int i, int st, int en, long val) {
        long cur = get(i, st, en);
        if (val < cur) {
            q.remove(new Val(cur, i, st, en));
            set(i, st, en, val);
            q.add(new Val(val, i, st, en));
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str;
        String[] params;

        str = br.readLine();
        params = str.split(" ");
        int G = Integer.parseInt(params[0]);
        int N = Integer.parseInt(params[1]);
        int M = Integer.parseInt(params[2]);
        int origG = G;

        ArrayList<Mutation> mutations = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            str = br.readLine();
            params = str.split(" ");
            int startGene = Integer.parseInt(params[0]);
            int len = Integer.parseInt(params[1]);

            if (len == 1) {
                int endGene = Integer.parseInt(params[2]);
                mutations.add(new Mutation(startGene, endGene));
            } else {
                int cur = startGene;
                int pos = 2;
                while (true) {
                    int nextGene = Integer.parseInt(params[pos]);
                    pos++;
                    len--;
                    if (len == 1) {
                        int finalGene = Integer.parseInt(params[pos]);
                        mutations.add(new Mutation(cur, nextGene, finalGene));
                        break;
                    }
                    mutations.add(new Mutation(cur, nextGene, G));
                    cur = G;
                    G++;
                }
            }
        }

        int[] mutationsByRhsSt = new int[G + 1];
        for (int i = 0; i <= G; i++) {
            mutationsByRhsSt[i] = 0;
        }
        for (int ind = 0; ind < mutations.size(); ind++) {
            Mutation rhs = mutations.get(ind);
            if ((rhs.en2 == null) || (rhs.en2.equals(rhs.en1))) {
                mutationsByRhsSt[rhs.en1]++;
            } else {
                mutationsByRhsSt[rhs.en1]++;
                mutationsByRhsSt[rhs.en2]++;
            }
        }
        for (int i = 1; i <= G; i++) {
            mutationsByRhsSt[i] += mutationsByRhsSt[i - 1];
        }
        int[] mutationsByRhs = new int[mutationsByRhsSt[G] + 1];
        for (int ind = 0; ind < mutations.size(); ind++) {
            Mutation rhs = mutations.get(ind);
            if ((rhs.en2 == null) || (rhs.en2.equals(rhs.en1))) {
                mutationsByRhsSt[rhs.en1]--;
                mutationsByRhs[mutationsByRhsSt[rhs.en1]] = ind;
            } else {
                mutationsByRhsSt[rhs.en1]--;
                mutationsByRhs[mutationsByRhsSt[rhs.en1]] = ind;
                mutationsByRhsSt[rhs.en2]--;
                mutationsByRhs[mutationsByRhsSt[rhs.en2]] = ind;
            }
        }

        Set<String> keywords = new HashSet<>();
        Set<String> prefixesSet = new HashSet<>();
        prefixesSet.add("");

        for (int i = 0; i < M; i++) {
            str = br.readLine();
            params = str.split(" ");
            int len = Integer.parseInt(params[0]);

            String s = "";
            for (int j = 0; j < len; j++) {
                int elem = Integer.parseInt(params[j + 1]);
                s += elem == 1 ? "1" : "0";
            }
            keywords.add(s);
            for (int j = 1; j <= len; j++) {
                prefixesSet.add(s.substring(0, j));
            }
        }

        ArrayList<String> prefixes = new ArrayList<>(prefixesSet.size());
        ArrayList<Boolean> prefixesIsTerminal = new ArrayList<>(prefixesSet.size());
        Map<String, Integer> indexes = new HashMap<>();
        for (String prefix : prefixesSet) {
            indexes.put(prefix, prefixes.size());
            prefixes.add(prefix);

            boolean isTerminal = false;
            for (int i = 0; i < prefix.length(); i++) {
                if (keywords.contains(prefix.substring(i))) {
                    isTerminal = true;
                }
            }

            prefixesIsTerminal.add(isTerminal);
        }

        int S = prefixes.size();

        for (int i = 0; i < G; i++) {
            for (int st = 0; st < S; st++) {
                for (int en = 0; en < S; en++) {
                    set(i, st, en, MYINFLL);
                }
            }
        }

        for (int st = 0; st < S; st++) {
            if (!prefixesIsTerminal.get(st)) {
                for (int i = 0; i < 2; i++) {
                    String s = prefixes.get(st) + (i == 0 ? "0" : "1");
                    while (!prefixesSet.contains(s)) {
                        s = s.substring(1);
                    }
                    int en = indexes.get(s);
                    if (!prefixesIsTerminal.get(en)) {
                        update(i, st, en, 1L);
                    }
                }
            }
        }

        while (true) {
            Val current = q.pollFirst();
            if (current == null) {
                break;
            }
            int i = current.i;
            int st = current.st;
            int en = current.en;
            long cur = current.value;

            for (int pos = mutationsByRhsSt[i]; pos < mutationsByRhsSt[i + 1]; pos++) {
                int ind = mutationsByRhs[pos];
                Mutation mutation = mutations.get(ind);
                if (mutation.en2 == null) {
                    update(mutation.st, st, en, cur);
                } else {
                    if (mutation.en1 == i) {
                        for (int md = 0; md < S; md++) {
                            update(mutation.st, st, md, cur + get(mutation.en2, en, md));
                        }
                    }
                    if (mutation.en2 == i) {
                        for (int md = 0; md < S; md++) {
                            update(mutation.st, md, en, get(mutation.en1, md, st) + cur);
                        }
                    }
                }
            }
        }

        for (int i = 2; i < origG; i++) {
            long res = MYINFLL;
            for (int en = 0; en < S; en++) {
                long cur = get(i, 0, en);
                if (cur < res) {
                    res = cur;
                }
            }
            if (res == MYINFLL) {
                bw.write("YES\n");
            } else {
                bw.write("NO ");
                bw.write(String.valueOf(res));
                bw.write("\n");
            }
        }

        bw.close();
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32
• Subtask 5: 18 / 18