A post on a board has n comments, numbered 1 to n in the order they were written.
A comment is written either directly on the post or as a reply to an earlier comment.
For comment i a number pᵢ is given. If pᵢ is 0 the comment is directly on the post; otherwise it is a reply to comment pᵢ. A reply is always to a comment with a smaller number.
The screen shows one comment per line in the following order.
Comments directly on the post are shown from the smallest number.
Right after a comment is shown, the replies to it are shown just below it from the smallest number.
Each reply follows the same rule: all replies under it are shown before moving on to the next reply.
For each comment you are told whether it is folded. If cᵢ is 1, comment i is folded.
A folded comment still shows its own line, but none of the replies to it, nor the replies under those replies, are shown.
Shown comments get line numbers 1, 2, 3, … from the top of the screen. Comments that are not shown take no line.
On the first line print the number of comments shown on the screen.
On the second line print the line numbers of comments 1 to n in order, separated by single spaces. Print 0 for a comment that is not shown.
Input
The first line has n, the second line p₁ … pₙ, and the third line c₁ … cₙ, separated by single spaces. 1 ≤ n ≤ 10,000, 0 ≤ pᵢ < i, cᵢ is 0 or 1. All are integers
Output
Line 1: the number of comments shown. Line 2: the line number of each of the n comments, or 0 if it is not shown
Example 1 · stdin
7
0 1 1 0 2 4 2
0 0 0 1 1 0 0
stdout
6
1 2 5 6 3 0 4
Example 2 · stdin
5
0 1 2 3 0
0 1 0 0 0
stdout
3
1 2 0 0 3
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The thread view is exactly the visiting order of depth-first search (DFS): print a comment, go all the way down through its replies, then come back and move to the next comment. In the first example the screen shows 1, 2, 5, 7, 3, 4, and comment 6 is not shown because comment 4 is folded (comment 5 is folded too, but it has no replies so nothing changes). Recursion is the shortest way to write it, but replies can chain 10,000 deep. Python stops with RecursionError because its recursion limit is 1,000 by default, and Craykon also stops after a few thousand levels. So all eight languages use an explicit stack: give the popped comment a line number and, if it is not folded, push its replies. Trap one: a stack returns the last thing pushed first, so push the replies from the largest number to get the smallest number out first. Pushing in number order shows siblings backwards. Trap two: using a queue (taking from the front) instead of a stack turns it into breadth-first search, which goes level by level, so a reply appears much later instead of right under its comment. Trap three: a folded comment still shows its own line. You just do not go down. Trap four: hiding only the direct replies of a folded comment is wrong — replies to those replies are hidden as well (comment 4 in the second example). Not going down gives this for free. Stacks differ by language: append/pop on a Python list, push/pop on a JavaScript/TypeScript array, push/pop of Java ArrayDeque, C# Stack<int>, C++ std::stack (read with top(), then remove with pop()), and in C an array of n + 1 slots with a top index, since each comment is pushed once. Craykon adds to a list with Add, reads stack[stack.Count - 1] and removes it with RemoveAt(stack.Count - 1). The C solution inserts each reply at the front of a linked list, so walking the list yields the largest number first and they can be pushed as they come.
Pythonmain.py · 27 lines
import sysdata = sys.stdin.read().split()n = int(data[0])parent = [0] + [int(x) for x in data[1:1 + n]] # parent[i] = i가 답한 댓글(0이면 글에 바로 단 댓글)folded = [0] + [int(x) for x in data[1 + n:1 + 2 * n]] # folded[i] = 1이면 접힌 댓글# replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다# replies[0]은 글에 바로 단 댓글들이다replies = [[] for _ in range(n + 1)]for i in range(1, n + 1): replies[parent[i]].append(i)# 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다# 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다line = [0] * (n + 1)shown = 0stack = replies[0][::-1]while stack: v = stack.pop() shown += 1 line[v] = shown if not folded[v]: # 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 stack.extend(reversed(replies[v]))print(shown)print(" ".join(map(str, line[1:])))
JavaScriptmain.js · 22 lines
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];// replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다// replies[0]은 글에 바로 단 댓글들이다const replies = Array.from({ length: n + 1 }, () => []);for (let i = 1; i <= n; i++) replies[data[i]].push(i);const folded = (v) => data[n + v] === 1; // 접힌 댓글인가// 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다// 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다const line = new Array(n + 1).fill(0);let shown = 0;const stack = [...replies[0]].reverse();while (stack.length > 0) { const v = stack.pop(); line[v] = ++shown; if (folded(v)) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 for (let k = replies[v].length - 1; k >= 0; k--) stack.push(replies[v][k]);}console.log(shown);console.log(line.slice(1).join(" "));
TypeScriptmain.ts · 24 lines
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];// replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다// replies[0]은 글에 바로 단 댓글들이다const replies: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 1; i <= n; i++) replies[data[i]].push(i);const folded = (v: number): boolean => data[n + v] === 1; // 접힌 댓글인가// 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다// 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다const line: number[] = new Array<number>(n + 1).fill(0);let shown = 0;const stack: number[] = [...replies[0]].reverse();while (stack.length > 0) { const v = stack.pop() as number; line[v] = ++shown; if (folded(v)) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 for (let k = replies[v].length - 1; k >= 0; k--) stack.push(replies[v][k]);}console.log(shown);console.log(line.slice(1).join(" "));
JavaMain.java · 42 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; // replies.get(v) = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다 // replies.get(0)은 글에 바로 단 댓글들이다 List<List<Integer>> replies = new ArrayList<>(); for (int v = 0; v <= n; v++) replies.add(new ArrayList<>()); for (int i = 1; i <= n; i++) { st.nextToken(); replies.get((int) st.nval).add(i); } boolean[] folded = new boolean[n + 1]; for (int i = 1; i <= n; i++) { st.nextToken(); folded[i] = st.nval == 1; } // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다 // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다 int[] line = new int[n + 1]; int shown = 0; ArrayDeque<Integer> stack = new ArrayDeque<>(); stack.push(0); // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다 while (!stack.isEmpty()) { int v = stack.pop(); if (v != 0) line[v] = ++shown; if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 List<Integer> r = replies.get(v); for (int k = r.size() - 1; k >= 0; k--) stack.push(r.get(k)); } StringBuilder sb = new StringBuilder(); sb.append(shown).append('\n'); for (int i = 1; i <= n; i++) sb.append(line[i]).append(i < n ? ' ' : '\n'); System.out.print(sb); }}
C#Main.cs · 38 lines
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]); // replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다 // replies[0]은 글에 바로 단 댓글들이다 var replies = new List<int>[n + 1]; for (int v = 0; v <= n; v++) replies[v] = new List<int>(); for (int i = 1; i <= n; i++) replies[int.Parse(data[i])].Add(i); var folded = new bool[n + 1]; for (int i = 1; i <= n; i++) folded[i] = data[n + i] == "1"; // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다 // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다 var line = new int[n + 1]; int shown = 0; var stack = new Stack<int>(); stack.Push(0); // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다 while (stack.Count > 0) { int v = stack.Pop(); if (v != 0) line[v] = ++shown; if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 for (int k = replies[v].Count - 1; k >= 0; k--) stack.Push(replies[v][k]); } var sb = new StringBuilder(); sb.Append(shown).Append('\n'); for (int i = 1; i <= n; i++) sb.Append(line[i]).Append(i < n ? ' ' : '\n'); Console.Write(sb); }}
C++main.cpp · 39 lines
#include <iostream>#include <stack>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 i를 차례로 넣으면 번호 순이 된다 // replies[0]은 글에 바로 단 댓글들이다 vector<vector<int>> replies(n + 1); for (int i = 1; i <= n; i++) { int p; cin >> p; replies[p].push_back(i); } vector<int> folded(n + 1, 0); for (int i = 1; i <= n; i++) cin >> folded[i]; // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다 // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다 vector<int> line(n + 1, 0); int shown = 0; stack<int> st; st.push(0); // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다 while (!st.empty()) { int v = st.top(); st.pop(); if (v != 0) line[v] = ++shown; if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 for (auto it = replies[v].rbegin(); it != replies[v].rend(); ++it) st.push(*it); } cout << shown << '\n'; for (int i = 1; i <= n; i++) cout << line[i] << (i < n ? ' ' : '\n'); return 0;}
Cmain.c · 38 lines
#include <stdio.h>#include <stdlib.h>int main(void) { int n; if (scanf("%d", &n) != 1) return 0; // 답글 목록을 배열 둘로: first[v]에서 시작해 next[i]로 따라간다(v = 0은 글 자체) // 새 답글을 목록의 맨 앞에 끼우므로, 따라가면 번호가 큰 답글부터 나온다 int *first = calloc(n + 1, sizeof(int)); int *next = calloc(n + 1, sizeof(int)); int *folded = calloc(n + 1, sizeof(int)); for (int i = 1; i <= n; i++) { int p; scanf("%d", &p); next[i] = first[p]; first[p] = i; } for (int i = 1; i <= n; i++) scanf("%d", &folded[i]); // 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다 // 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다 int *line = calloc(n + 1, sizeof(int)); int *stack = malloc((n + 1) * sizeof(int)); // 댓글마다 한 번만 들어간다 int top = 0, shown = 0; stack[top++] = 0; // 0번은 글 자체: 줄을 차지하지 않고 접히지도 않는다 while (top > 0) { int v = stack[--top]; if (v != 0) line[v] = ++shown; if (folded[v]) continue; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 for (int r = first[v]; r != 0; r = next[r]) stack[top++] = r; } printf("%d\n", shown); for (int i = 1; i <= n; i++) printf(i > 1 ? " %d" : "%d", line[i]); printf("\n"); free(first); free(next); free(folded); free(line); free(stack); return 0;}
Craykonmain.cray · 51 lines
n = Console.ReadNumbers()[0];parent = Console.ReadNumbers(); // parent[i - 1] = i번 댓글이 답한 댓글(0이면 글에 바로 단 댓글)folded = Console.ReadNumbers(); // folded[i - 1] = 1이면 접힌 댓글// 목록은 10,000칸까지라 댓글 번호에서 1을 빼 0번부터 둔다// replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 차례로 넣으면 번호 순이 된다replies = [];for (v = 0; v < n; v++){ replies.Add([]);}tops = []; // 글에 바로 단 댓글들for (i = 0; i < n; i++){ if (parent[i] == 0) { tops.Add(i); } else { replies[parent[i] - 1].Add(i); }}// 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다// 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다line = NewList(n, 0);shown = 0;stack = [];for (k = tops.Count - 1; k >= 0; k--){ stack.Add(tops[k]);}while (stack.Count > 0){ v = stack[stack.Count - 1]; stack.RemoveAt(stack.Count - 1); shown += 1; line[v] = shown; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 if (folded[v] == 0) { for (k = replies[v].Count - 1; k >= 0; k--) { stack.Add(replies[v][k]); } }}Console.WriteLine(shown);Console.WriteLine(line);