Nathan O. Davis has been running an electronic bulletin board system named JAG-channel.…
- User
Nathan O. Davis has been running an electronic bulletin board system named JAG-channel. He is now having hard time to add a new feature there --- threaded view.
Like many other bulletin board systems, JAG-channel is thread-based. Here a thread (also called a topic) refers to a single conversation with a collection of posts. Each post can be an opening post, which initiates a new thread, or a reply to a previous post in an existing thread.
Threaded view is a tree-like view that reflects the logical reply structure among the posts: each post forms a node of the tree and contains its replies as its subnodes in the chronological order (i.e. older replies precede newer ones). Note that a post along with its direct and indirect replies forms a subtree as a whole.
Let us take an example. Suppose: a user made an opening post with a message
hoge; another user replied to it withfuga; yet another user also replied to the opening post withpiyo; someone else replied to the second post (i.e.fuga”) withfoobar; and the fifth user replied to the same post withjagjag. The tree of this thread would look like:hoge ├─fuga │ ├─foobar │ └─jagjag └─piyo
For easier implementation, Nathan is thinking of a simpler format: the depth of each post from the opening post is represented by dots. Each reply gets one more dot than its parent post. The tree of the above thread would then look like:
hoge .fuga ..foobar ..jagjag .piyo
Your task in this problem is to help Nathan by writing a program that prints a tree in the Nathan's format for the given posts in a single thread. Input
Input contains a single dataset in the following format:
n k_1 M_1 k_2 M_2 : : k_n M_n
The first line contains an integer n (1 ≤ n ≤ 1,000), which is the number of posts in the thread. Then 2n lines follow. Each post is represented by two lines: the first line contains an integer k_i (k_1 = 0, 1 ≤ k_i < i for 2 ≤ i ≤ n) and indicates the i-th post is a reply to the k_i-th post; the second line contains a string M_i and represents the message of the i-th post. k_1 is always 0, which means the first post is not replying to any other post, i.e. it is an opening post.
Each message contains 1 to 50 characters, consisting of uppercase, lowercase, and numeric letters.
Output
Print the given n messages as specified in the problem statement.
Sample Input 1
1 0 icpc
Output for the Sample Input 1
icpc
Sample Input 2
5 0 hoge 1 fuga 1 piyo 2 foobar 2 jagjag
Output for the Sample Input 2
hoge .fuga ..foobar ..jagjag .piyo
Sample Input 3
8 0 jagjag 1 hogehoge 1 buhihi 2 fugafuga 4 ponyoponyo 5 evaeva 4 nowawa 5 pokemon
Output for the Sample Input 3
jagjag .hogehoge ..fugafuga ...ponyoponyo ....evaeva ....pokemon ...nowawa .buhihi
Sample Input 4
6 0 nakachan 1 fan 2 yamemasu 3 nennryou2 4 dannyaku4 5 kouzai11
Output for the Sample Input 4
nakachan .fan ..yamemasu ...nennryou2 ....dannyaku4 .....kouzai11
Sample Input 5
34 0 LoveLive 1 honoka 2 borarara 2 sunohare 2 mogyu 1 eri 6 kasikoi 7 kawaii 8 eriichika 1 kotori 10 WR 10 haetekurukotori 10 ichigo 1 umi 14 love 15 arrow 16 shoot 1 rin 18 nyanyanya 1 maki 20 6th 20 star 22 nishikino 1 nozomi 24 spiritual 25 power 1 hanayo 27 darekatasukete 28 chottomattete 1 niko 30 natsuiro 30 nikkonikkoni 30 sekaino 33 YAZAWA
Output for the Sample Input 5
LoveLive .honoka ..borarara ..sunohare ..mogyu .eri ..kasikoi ...kawaii ....eriichika .kotori ..WR ..haetekurukotori ..ichigo .umi ..love ...arrow ....shoot .rin ..nyanyanya .maki ..6th ..star ...nishikino .nozomi ..spiritual ...power .hanayo ..darekatasukete ...chottomattete .niko ..natsuiro ..nikkonikkoni ..sekaino ...YAZAWA
Sample Input 6
6 0 2ch 1 1ostu 1 2get 1 1otsu 1 1ostu 3 pgr
Output for the Sample Input 6
2ch .1ostu .2get ..pgr .1otsu .1ostu
Example
Input
1 0 icpc
Output
icpc
Assistant
We are asked to write a program that prints messages in a threaded view, given the data of posts: for each post i (1-indexed), we have k_i (the index of the post it replies to, with k_1=0 indicating root), and then M_i (message string). We need to output each message prefixed by a number of dots corresponding to its depth in the reply tree, where root depth 0 (no dot), each child depth = parent depth +1, etc., and the order should be the given order? Wait careful: The problem statement says: "Your task ... is to ... print a tree in the Nathan's format for the given posts in a single thread." The input gives the posts in the order they appear? Actually, the posts are numbered from 1 to n, and the dataset lists them sequentially. For each i, k_i is given. The sample outputs show that the output order is the same as the input order? Let's examine sample 2:
Input: 5 0 hoge 1 fuga 1 piyo 2 foobar 2 jagjag
That yields output: hoge .fuga ..foobar ..jagjag .piyo
The order of output is: post1, post2, post4, post5, post3. That's not the same as input order (1,2,3,4,5). Actually input order is 1,2,3,4,5. Output order is 1,2,4,5,3. So they are not preserving input order; they are printing in a traversal order of the tree, specifically preorder? Let's see: Tree: root hoge, children: fuga (post2) and piyo (post3). Under fuga: children foobar (post4) and jagjag (post5). In output, we see: root, then child fuga, then its children foobar, jagjag, then piyo. That's a depth-first preorder traversal where children are visited in the order of their creation (chronological order). The problem statement says: "Threaded view is a tree-like view that reflects the logical reply structure among the posts: each post forms a node of the tree and contains its replies as its subnodes in the chronological order (i.e. older replies precede newer ones)." And "For easier implementation, Nathan is thinking of a simpler format: the depth of each post from the opening post is represented by dots. ... The tree of the above thread would then look like:
hoge .fuga ..foobar ..jagjag .piyo"
Thus the output is a tree representation where children are listed under parent, in chronological order (i.e., the order in which the posts were made, which is presumably the input order because posts are listed chronologically?). Since posts are given in chronological order (i-th post appears later), the children of a parent appear in the order they were posted. That corresponds to a preorder traversal: you output a node, then recursively output its children in the order they appear. However note: In the output, we have to output each message with the correct number of dots. That is exactly the preorder of the tree, where we also output the depth. But what about the order of posts that are not in root? For example, sample 3:
Input: 8 0 jagjag 1 hogehoge 1 buhihi 2 fugafuga 4 ponyoponyo 5 evaeva 4 nowawa 5 pokemon
Output: jagjag .hogehoge ..fugafuga ...ponyoponyo ....evaeva ....pokemon ...nowawa .buhihi
Let's reconstruct: post1 root jagjag depth0. post2 replies to 1 => child of 1, depth1 => .hogehoge. post3 replies to 1 => child of 1, depth1 => .buhihi? But output shows after .hogehoge and its subtree, then .buhihi at the end. That matches: child order: post2 then post3 (chronological). Under post2 (hogehoge), children: post4 replies to 2 => ..fugafuga; then post5 replies to? Actually post5 replies to? In input: line after post4: "4" then "ponyoponyo"? Wait re-check sample 3 from problem:
Sample Input 3 8 0 jagjag 1 hogehoge 1 buhihi 2 fugafuga 4 ponyoponyo 5 evaeva 4 nowawa 5 pokemon
Let's parse carefully:
n=8 post1: k1=0, M1=jagjag post2: k2=1, M2=hogehoge (reply to post1) post3: k3=1, M3=buhihi (reply to post1) post4: k4=2, M4=fugafuga (reply to post2) post5: k5=4, M5=ponyoponyo? Actually from the data: after post4 we have "4" and then "ponyoponyo"? Let's read lines:
post1: k=0, M=jagjag post2: k=1, M=hogehoge post3: k=1, M=buhihi post4: k=2, M=fugafuga post5: k=4, M=ponyoponyo? Actually after "2" then "fugafuga" then next is "4" then "ponyoponyo"? The sample input lines: 8 0 jagjag 1 hogehoge 1 buhihi 2 fugafuga 4 ponyoponyo 5 evaeva 4 nowawa 5 pokemon
So: post1: k1=0, M1=jagjag post2: k2=1, M2=hogehoge post3: k3=1, M3=buhihi post4: k4=2, M4=fugafuga post5: k5=4, M5=ponyoponyo post6: k6=5, M6=evaeva post7: k7=4, M7=nowawa post8: k8=5, M8=pokemon
So tree: root1; children: 2,3 (in order). Node2 children: 4,7? Actually 4 is child of 2, 7 is also child of 2? k7=4? Wait k7=4, which means reply to post4 (fugafuga). So node4 children: 5 and 7? Actually post5 is child of 4, post7 is also child of 4? k7=4 yes. And post5 (ponyoponyo) children: post6 (evaeva) with k6=5, and post8 (pokemon) with k8=5. So subtree: 4 has children 5 and 7? But 7 is after post5? Chronologically: post4 (fugafuga) then post5 (ponyoponyo) then post6 (evaeva) then post7 (nowawa) then post8 (pokemon). Node4 children in chronological order: those that have k_i=4: which are post5 and post7? Actually check: post5 k=4, post7 k=4, so both children of node4. Their order: post5 before post7. So under node4: first child post5 (ponyoponyo), then child post7 (nowawa). Under post5: children post6 (evaeva) and post8 (pokemon). So the output should be:
root .2 (hogehoge) ..4 (fugafuga) ...5 (ponyoponyo) ....6 (evaeva) ....8 (pokemon) ...7 (nowawa) .3 (buhihi)
But the output given:
jagjag .hogehoge ..fugafuga ...ponyoponyo ....evaeva ....pokemon ...nowawa .buhihi
Matches exactly: after ...ponyoponyo we have ....evaeva, ....pokemon, then ...nowawa, then .buhihi.
Thus the output order is a preorder traversal (node, then recursively children in chronological order). That is typical for tree representation. So we need to output each node exactly once in that order. The input gives us the tree structure via parent indices. We need to output messages with dots depth times.
So algorithm: read n. For i=1..n, read k_i (int) and M_i (string). We need to construct tree: each node has list of children. Since children must be in chronological order (i.e., the order they appear in input), we can simply when processing each i (except root), add i as a child of parent k_i, in the order they appear (i increasing). That yields children lists already sorted by time (since i increases). Then perform a DFS (preorder) from root (node 1) and output each node with '.' repeated depth times then message. That's straightforward.
Constraints: n <= 1000, so recursion depth up to 1000 (worst-case line chain) but okay. Use iterative if needed, but recursion fine in most languages.
Edge cases: root always has k=0. There is exactly one root (post1). Guaranteed that tree is connected? Possibly there could be multiple roots? Since k_i < i and k_1=0, and for i>1, 1 <= k_i < i, so all later posts refer to earlier posts. So it's a tree (connected, directed from parent to child). Indeed it forms a rooted tree with root 1.
Therefore solution: Build adjacency list vector children[1001]. For i from 1 to n, read k_i and M_i. If k_i != 0, children[k_i].push_back(i). Store messages in array msgs[1001] (1-indexed). Then DFS(1,0): output dots depth times, then msgs[node]; then for each child in children[node] (in order they were added, which is increasing i, i.e., chronological), call DFS(child, depth+1).
That's it.
But wait: Sample 6:
Input: 6 0 2ch 1 1ostu 1 2get 1 1otsu 1 1ostu 3 pgr
According to description: root 1: "2ch". children of 1: posts 2,3,4,5? Let's list:
post1: k1=0, M1=2ch post2: k2=1, M2=1ostu post3: k3=1, M3=2get post4: k4=1, M4=1otsu post5: k5=1, M5=1ostu post6: k6=3, M6=pgr
So children of 1: nodes 2,3,4,5 in order. Node3 has child 6. Output given:
2ch .1ostu .2get ..pgr .1otsu .1ostu
Yes, that matches our algorithm.
Thus solution is simple.
One nuance: The problem may have input with multiple lines; need to read using standard input.
Complexities: O(n).
Implementation:
- Use vector<vector> children(n+1);
- string msg[n+1];
- For i=1..n: read k (int), maybe newline, then read message (string). The message may contain spaces? The problem says: "Each message contains 1 to 50 characters, consisting of uppercase, lowercase, and numeric letters." So no spaces, so can read with cin >> string.
- Then DFS.
Be careful about recursion depth: n up to 1000, okay.
Alternatively, we could compute depths using DP and then output in order of nodes? But we need preorder, not input order. So DFS is needed.
Since we have the children lists, we can do an explicit stack to avoid recursion, but recursion is fine.
Pseudo:
#include #include #include using namespace std;
vector children[1001]; string msg[1001];
void dfs(int node, int depth) { for (int i=0; i<depth; i++) cout << "."; cout << msg[node] << "\n"; for (int child : children[node]) { dfs(child, depth+1); } }
int main() { int n; cin >> n; for (int i=1; i<=n; i++) { int k; cin >> k; cin >> msg[i]; if (k != 0) children[k].push_back(i); } dfs(1, 0); return 0; }
That's it.
Now, we must produce answer in appropriate language. The problem is from "ICPC 2017 Asia Regional – Japan JAG Summer 2017 Day2"? Actually it's from "JAG Practice Contest for ACM-ICPC Asia Regional 2017"? Anyway, we just need to write a solution.
But let's also check sample 5 to see if there is any trick: It's large but consistent.
Thus the answer is straightforward.
But wait: The problem statement says "Your task ... is to ... print a tree in the Nathan's format for the given posts in a single thread." And the input gives n and then for each post, we have k_i and M_i. The sample outputs match the DFS preorder.
Thus we can produce the solution.
Now, implement in Python for simplicity? The problem might expect C++ but we can produce any language. The user didn't specify language. Usually we answer with solution in C++ or Python. For clarity, I'll write solution in Python.
But careful: Python recursion depth default is about 1000, which may be borderline but n <= 1000, and recursion depth could be up to n (chain). Python's recursion limit is typically 1000, which may cause RecursionError. So we should increase recursion limit: import sys; sys.setrecursionlimit(2000). Or we can implement iterative DFS using stack. But I'll set recursion limit higher.
Alternatively, we can compute depths and order using stack: we can simulate preorder.
Approach: Since children are already added in chronological order, we can just do:
stack = [(1,0)] # node, depth while stack: node, depth = stack.pop() # need to output before children, but we need to pop from stack in order such that children are processed in correct order (preorder, left-to-right). Since stack is LIFO, we push children in reverse order. # Or we can use recursion.
Simplify: use recursion with sys.setrecursionlimit(2000).
Let's implement.
Pseudo:
import sys sys.setrecursionlimit(20000)
def dfs(u, depth): print('.' * depth + msg[u]) for v in children[u]: dfs(v, depth+1)
def main(): data = sys.stdin.read().split() # parse: first token n, then for i in range(n): ki, Mi # messages are alphanumeric, so tokens separated by whitespace. it = iter(data) n = int(next(it)) msg = [None] * (n+1) children = [[] for _ in range(n+1)] for i in range(1, n+1): k = int(next(it)) mi = next(it) msg[i] = mi if k != 0: children[k].append(i) dfs(1,0)
if name == "main": main()
That should work.
Check sample: For input with 1, prints "icpc". Good.
Edge cases: n=1, root only.
Thus solution.
We can also produce in C++.
Now, produce final answer with explanation.
Given the problem is simple, but we need to output the code.
In the final response, we will provide a clear explanation and then the code in Python (or C++). I'll choose Python because it's concise.
Make sure to include reading from standard input and printing output.
Ok. We need to output the threaded view of posts. Each post replies to a previous post, forming a tree rooted at post 1. The output must list messages in a preorder traversal (root, then recursively each child in chronological order) with a number of dots equal to the depth.
We build a tree from the input: for each post i (i≥2) with parent k_i, we add i as a child of k_i. Children are stored in the order they appear, which is chronological. Then a depth‑first search from the root prints each message with the appropriate prefix.
import sys sys.setrecursionlimit(10000) # to handle up to 1000 levels def dfs(node: int, depth: int): print('.' * depth + msg[node]) for child in children[node]: dfs(child, depth + 1) def main(): data = sys.stdin.read().split() if not data: return it = iter(data) n = int(next(it)) global msg, children msg = [''] * (n + 1) children = [[] for _ in range(n + 1)] for i in range(1, n + 1): k = int(next(it)) m = next(it) msg[i] = m if k != 0: children[k].append(i) dfs(1, 0) if __name__ == '__main__': main()