시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB29171359.091%

문제

Professor Oak, the friendly neighbourhood Pokémon Professor, has been getting a lot of questions about Pokémon ancestors lately.

One of the things a lot of Pokémon trainers are curious about is finding common ancestors of Pokémon in their Pokédex. In particular, each Pokémon Trainer wants to know about the number of Pokémon that are ancestors of exactly L of their Pokémon. The value of L, too, is decided by the trainer asking the question.

In Pokémon world, given the genome strings of Pokémon A and Pokémon B, Pokémon A is considered an ancestor of Pokémon B if and only if the genome string of Pokémon A is a prefix of Pokémon B’s genome string. Also, all non-empty genome strings correspond to a real Pokémon in the Pokémon world.

Given Professor Oak’s database of Pokémon genomes, help him answer the trainers’ queries.

입력

The first line of input will contain the integer N, (1 ≤ N ≤ 200 000), the number of Pokémon in Professor Oak’s database, and the integer Q, (1 ≤ Q ≤ 200 000), the number of Pokémon trainers that have questions for Professor Oak. The following N lines contain a string, each denoting a Pokémon genome string from Professor Oak’s database. All genome strings are distinct and consist of lowercase English letters.

Then 2 · Q lines follow. Two lines describe each Pokémon trainer’s query. The first line of each query contains two integers: K, (1 ≤ K ≤ N), the number of Pokémon they own, and L, (1 ≤ L ≤ K), the value described in the statement. The second line contains K distinct space-separated integers. An integer x in the list of K integers indicates that this trainer owns the xth Pokémon from Professor Oak’s database, where the Pokémon Professor Oak owns are numbered from 1 to N.

The sum of the lengths of the genome strings in input does not exceed 200 000 characters and the sum of K over all queries does not exceed 1 000 000.

출력

For each Pokémon trainer’s query, print the number of Pokémon that are ancestors of exactly L of the K Pokémon they own. Assume that all non-empty genome strings correspond to a Pokémon. Note that L is defined in the query, and does not necessarily remain the same for all queries.

예제 입력 1

5 2
nib
abcd
abee
abced
nit
4 2
1 2 5 3
3 2
2 3 4

예제 출력 1

4
1

힌트

There are five Pokémon in Professor Oak’s database: “nib”, “abcd”, “abee”, “abced”, and “nit”. There are two trainers with queries.

The first Pokémon trainer owns Pokémon with genome strings “nib”, “abcd”, “nit”, and “abee”, and would like to know how many ancestors there are of exactly two of her Pokémon. Pokémon with genome strings “a” and “ab” are ancestors of “abcd” and “abee”, and Pokémon with genome strings “n” and “ni” are ancestors of “nib” and “nit”, therefore the answer is 4.

The second Pokémon trainer owns Pokémon with genome strings “abcd”, “abee”, and “abced”, and would also like to know how many ancestors there are of exactly two of her Pokémon. Only the Pokémon with genome string “abc” is an ancestor of exactly 2 of the owned Pokémon, “abcd” and “abced”, therefore the answer is 1.

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 2018 A번

  • 문제를 만든 사람: Nalin Bhardwaj