레이팅 미적용베시는 곧 있을 어휘 퀴즈를 준비하는 엘시를 돕고 있다. 시험에 나올 단어들은 서로 다른 단어 \(M\)개로 이루어진 단어장에서 뽑히며, 단어장의 어떤 단어도 단어장의 다른 단어의 접두사가 아니다.
단어장이 비어 있지 않은 동안, 베시는 단어장에서 단어 하나를 골라 단어장에서 제거한 뒤, 그 단어를 왼쪽에서 오른쪽으로 한 글자씩 엘시에게 읽어 준다. 엘시의 임무는 그 단어를 유일하게 식별할 수 있게 되는 순간 베시에게 알리는 것이고, 그러면 베시는 읽기를 멈춘다.
베시는 단어장의 단어들을 \(w_1,w_2,\dots,w_M\) 순서로 읽기로 이미 정했다. 엘시가 가능한 한 빨리 답한다면, 베시는 각 단어의 몇 글자를 읽게 될까?
단어들은 압축된 형식으로 주어진다. 먼저 서로 다른 단어 \(N+1\)개(\(1\le N\le 10^6\))를 정의하고, 단어장은 그중 다른 단어의 접두사가 아닌 모든 단어로 이루어진다. 단어들은 다음과 같이 정의된다.
- 처음에 \(0\)번째 단어는 빈 문자열이다.
- 그다음 각 \(1\le i\le N\)에 대해, \(i\)번째 단어는 \(p_i\)번째 단어의 끝에 문자 하나를 덧붙인 것과 같다(\(0\le p_i
Problem credits: Benjamin Qi
배점
- 입력 4-5: 길이가 \(20\)보다 큰 단어는 없다.
- 입력 6-10: 단어장의 모든 단어의 길이의 합은 \(10^7\)을 넘지 않는다.
- 입력 11-18: 추가 제약이 없다.
Problem credits: Benjamin Qi
첫째 줄에 \(N\)이 주어진다. 압축된 형식으로 주어지는 단어의 수는 \(N+1\)이다.
다음 줄에 \(p_1,p_2,\dots,p_N\)이 주어진다. \(p_i\)는 \(i\)번째 단어가 \(p_i\)번째 단어의 끝에 문자 하나를 덧붙여 만들어짐을 나타낸다.
다른 어떤 단어의 접두사도 아닌 단어의 수를 \(M\)이라 하자. 다음 \(M\)개의 줄에 \(w_1,w_2,\dots,w_M\)이 주어지며, 이는 \(w_i\)번째 단어가 \(i\)번째로 읽힐 것임을 의미한다. 읽을 단어들이 단어장의 단어들의 순열을 이룸이 보장된다.
\(M\)개의 줄을 출력한다. \(i\)번째 줄에 베시가 읽게 되는 \(i\)번째 단어의 글자 수를 출력한다.
5
0 1 2 3 4
50There 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.
4
0 0 1 1
4
3
22
1
0The 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.
4
0 0 1 1
2
3
41
2
0riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > February > Silver