Submission #684638

# Submission time Handle Problem Language Result Execution time Memory
684638 2023-01-22T08:42:26 Z abhayptsr Selling RNA Strands (JOI16_selling_rna) Java 11
0 / 100
139 ms 12048 KB
import java.io.*;
import java.util.*;

class Main {
    static int mod = (int) (1e9 + 7);
    static PrintWriter out = new PrintWriter(System.out);

    public static class Trie {
        private class Node {
            Node A;
            Node U;
            Node G;
            Node C;
            boolean isend = false;
            HashSet<Integer> set = new HashSet<>();

            public String toString() {
                StringBuilder sb = new StringBuilder();
                if (A != null) {
                    sb.append("A | ");
                }
                if (U != null) {
                    sb.append("U | ");
                }
                if (G != null) {
                    sb.append("G | ");
                }
                if (C != null) {
                    sb.append("C | ");
                }
                sb.append(set);
                sb.append("\n");
                return sb.toString();
            }
        }

        /** Initialize your data structure here. */
        Node root;

        public Trie() {
            root = new Node();
        }

        public String toString() {
            Node curr = root;
            StringBuilder sb = new StringBuilder();
            Queue<Node> qu = new ArrayDeque<>();
            qu.add(curr);
            while (qu.size() != 0) {
                Node rem = qu.remove();
                sb.append(rem);
                if (rem.A != null) {
                    qu.add(rem.A);
                }
                if (rem.U != null) {
                    qu.add(rem.U);
                }
                if (rem.G != null) {
                    qu.add(rem.G);
                }
                if (rem.C != null) {
                    qu.add(rem.C);
                }
            }
            return sb.toString();
        }

        /** Inserts a word into the trie. */
        public void insert(String word, int idx) {
            Node curr = root;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                curr.set.add(idx);
                if (ch == 'A') {
                    if (curr.A == null) {
                        curr.A = new Node();
                    }
                    curr = curr.A;
                } else if (ch == 'U') {
                    if (curr.U == null) {
                        curr.U = new Node();
                    }
                    curr = curr.U;
                } else if (ch == 'G') {
                    if (curr.G == null) {
                        curr.G = new Node();
                    }
                    curr = curr.G;
                } else if (ch == 'C') {
                    if (curr.C == null) {
                        curr.C = new Node();
                    }
                    curr = curr.C;
                }
            }
            curr.set.add(idx);
            curr.isend = true;
        }

        public HashSet<Integer> query(String s) {
            Node curr = root;
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == 'A') {
                    if (curr.A == null) {
                        return new HashSet<>();
                    }
                    curr = curr.A;
                } else if (ch == 'U') {
                    if (curr.U == null) {
                        return new HashSet<>();
                    }
                    curr = curr.U;
                } else if (ch == 'G') {
                    if (curr.G == null) {
                        return new HashSet<>();
                    }
                    curr = curr.G;
                } else if (ch == 'C') {
                    if (curr.C == null) {
                        return new HashSet<>();
                    }
                    curr = curr.C;
                }
            }

            return curr.set;
        }
        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
    }

    static void solve() {
        int n = i();
        int m = i();
        Trie t1 = new Trie();
        Trie t2 = new Trie();
        for (int i = 0; i < n; i++) {
            String s = s();
            t1.insert(s, i);
            String rev = reverses(s);
            t2.insert(rev, i);
        }
        for (int i = 0; i < m; i++) {
            String L = s();
            String R = s();
            R=reverses(R);
            HashSet<Integer> set1 = t1.query(L);
            HashSet<Integer> set2 = t2.query(R);
            // System.err.println(set1 + " " + set2);
            int ans=0;
            for(int val:set1){
                if(set2.contains(val)){
                    ans++;
                }
            }
            out.println(ans);
        }
        // System.err.println(t2);
        // System.err.println(t1);
    }

    private static String reverses(String s) {
        StringBuilder sb = new StringBuilder();
        sb.append(s);
        sb.reverse();
        return sb.toString();
    }

    public static void main(String[] args) {
        int test = 1;
        while (test-- > 0) {
            solve();
        }
        out.flush();
        out.close();
    }

    // ------> swap(long[]arr,int idx1,int idx2)<---- swap int

    // ----->segmentTree--> segTree as class

    // ----->lazy_Seg_tree --> lazy_Seg_tree as class

    // -----> Trie --->Trie as class

    // ----->fenwick_Tree ---> fenwick_Tree

    // -----> POWER ---> long power(long x, long y) <----

    // -----> LCM ---> long lcm(long x, long y) <----

    // -----> GCD ---> long gcd(long x, long y) <----

    // -----> SIEVE --> ArrayList<Integer> sieve(int N) <-----

    // -----> NCR ---> long ncr(int n, int r) <----

    // -----> BINARY_SEARCH ---> int binary_Search(long[]arr,long x) <----

    // -----> (SORTING OF LONG, CHAR,INT) -->long[] sortLong(long[] a2)<--

    // ----> DFS ---> void dfs(ArrayList<ArrayList<Integer>>edges,int child,int
    // parent)<---

    // ---> NODETOROOT --> ArrayList<Integer>
    // node2Root(ArrayList<ArrayList<Integer>>edges,int child,int parent,int tofind)
    // <--

    // ---> LEVELS_TREE -->levels_Trees(ArrayList<HashSet<Integer>> edges, int
    // child, int parent,int[]level,int currLevel) <--

    // ---> K_THPARENT --> int k_thparent(int node,int[][]parent,int k) <---

    // ---> TWOPOWERITHPARENTFILL --> void twoPowerIthParentFill(int[][]parent) <---

    // -----> (INPUT OF INT,LONG ,STRING) -> int i() long l() String s()<-
    // tempstart

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int Int() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String String() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return String();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static InputReader in = new InputReader(System.in);

    public static int i() {
        return in.Int();
    }

    public static long l() {
        String s = in.String();
        return Long.parseLong(s);
    }

    public static String s() {
        return in.String();
    }

    public static int compareChar(char a, char b) {
        return Character.compare(a, b);
    }

    public static int compareInt(int a, int b) {
        return Integer.compare(a, b);
    }

    public static int compareLong(long a, long b) {
        return Long.compare(a, b);
    }

    public static boolean compareString(String a, String b) {
        return a.equals(b);
    }

    public static boolean compareStringBuilder(StringBuilder a, StringBuilder b) {
        return a.equals(b);
    }

}
# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 12048 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 129 ms 11796 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 139 ms 11976 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 12048 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -