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 行
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 行
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 行
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 行
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 行
#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 行
#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 行
n = 控制台.读数字()[0];parent = 控制台.读数字(); // parent[i - 1] = i번 댓글이 답한 댓글(0이면 글에 바로 단 댓글)folded = 控制台.读数字(); // folded[i - 1] = 1이면 접힌 댓글// 목록은 10,000칸까지라 댓글 번호에서 1을 빼 0번부터 둔다// replies[v] = v에 달린 답글들. 답글은 늘 번호가 더 크니 차례로 넣으면 번호 순이 된다replies = [];循环 (v = 0; v < n; v++){ replies.添加([]);}tops = []; // 글에 바로 단 댓글들循环 (i = 0; i < n; i++){ 如果 (parent[i] == 0) { tops.添加(i); } 否则 { replies[parent[i] - 1].添加(i); }}// 깊이 우선 탐색(DFS)을 스택으로: 꺼낸 차례가 곧 화면의 줄 차례다// 스택은 나중에 넣은 것이 먼저 나오니 번호가 큰 것부터 넣어야 작은 번호가 먼저 나온다line = 新列表(n, 0);shown = 0;stack = [];循环 (k = tops.数量 - 1; k >= 0; k--){ stack.添加(tops[k]);}当 (stack.数量 > 0){ v = stack[stack.数量 - 1]; stack.按位置移除(stack.数量 - 1); shown += 1; line[v] = shown; // 접힌 댓글은 자기 줄만 보이고 답글로는 내려가지 않는다 如果 (folded[v] == 0) { 循环 (k = replies[v].数量 - 1; k >= 0; k--) { stack.添加(replies[v][k]); } }}控制台.输出(shown);控制台.输出(line);