#PU1495. USACO 2025 February Contest, Silver — Problem 2. Vocabulary Quiz

    ID: 1428 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:feb25来源:usaco.orgscoring:equal_test_cases字典树枚举

USACO 2025 February Contest, Silver — Problem 2. Vocabulary Quiz

USACO 2025 February Contest, Silver — Problem 2. Vocabulary Quiz

题目描述

Bessie is helping Elsie with her upcoming vocabulary quiz. The words to be tested will be drawn from a bank of MM distinct words, where no word in the bank is a prefix of another word in the bank. While the bank is nonempty, Bessie will select a word from the bank, remove it from the bank, and read it to Elsie one character at a time from left to right. Elsie's task is to tell Bessie once she can uniquely identify it, after which Bessie will stop reading. Bessie has already decided to read the words from the word bank in the order w1,w2,…,wMw_1,w_2,\dots,w_M. If Elsie answers as quickly as possible, how many characters of each word will Bessie read? The words are given in a compressed format. We will first define N+1N+1 (1≤N≤1061\le N\le 10^6) distinct words, and then the word bank will consist of all those words that are not a prefix of another word. The words are defined as follows: Initially, the 00th word will be the empty string. Then for each 1≤i≤N1\le i\le N, the iith word will be equal to the pip_ith word plus an additional character at the end (0≤pi<i0\le p_i<i). The characters are chosen such that all N+1N+1 words are distinct.

输入格式

The first line contains NN, where N+1N+1 is the number of words given in the compressed format. The next line contains p1,p2,…,pNp_1,p_2,\dots,p_N where pip_i represents that the ii-th word is formed by taking the pip_i-th word and adding a single character to the end. Let MM be the number of words that are not a prefix of some other word. The next MM lines will contain w1,w2,…,wMw_1,w_2,\dots,w_M, meaning that the wiw_ith word will be the iith to be read. It is guaranteed that the words to be read form a permutation of the words in the word bank.

输出格式

(见题面原文)

数据范围

Inputs 4-5: No word has length greater than 2020. Inputs 6-10: The sum of the lengths of all words in the word bank does not exceed 10710^7. Inputs 11-18: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

5
0 1 2 3 4
5
0
There are $6$ words labeled $0\dots 5$. Word $5$ is the only one that is not  a
prefix of another word, so it is the only one in the bank. In general, once only
one word is left in the bank, Elsie won't need any characters to identify it.

样例 2

4
0 0 1 1
4
3
2
2
1
0
The bank consists of words $2$, $3$, and $4$.
Elsie needs two characters to identify word $4$ since words $3$ and $4$ share
their first character in common.
Once Bessie reads the first character of word $3$, Elsie has enough characters
to uniquely identify it, since word $4$ was already read.

样例 3

4
0 0 1 1
2
3
4
1
2
0