QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 1024 MB 總分: 100

#5615. 两张图合二为一

统计

当企业感到臃肿并需要重组时,他们会请来著名的重组顾问 Don Sizing。Don 提出的首要要求之一是提供一张显示部门层级的图表,即哪些部门负责管理其他部门。关于这个层级结构,往往会产生一些混淆,导致 Don 最终得到两张或多张显示相同部门集合的不同图表。在这种情况下,Don 必须确定这些图表是否相似,即它们是否展示了完全相同的层级关系,尽管它们的绘制方式可能不同。例如,考虑图 1 左侧所示的两张图表。虽然它们看起来不同,但它们代表了相同的层级关系——部门 11 负责管理部门 10 和 12,而部门 12 负责管理部门 13、17 和 28。图 1 右侧的三张图表则完全不同,每一张都代表了不同的层级关系。

图 1:两组层级图表。

对于部门数量较少的公司,确定两张图表是否相同相对简单,但对于大型公司来说,这可能相当困难。Don 已经评估了这个问题,并决定需要一些软件来为他解决这个问题。

输入格式

输入包含两行,每一行代表一个层级图表。层级图表的语法如下:

  1. 一个单独的部门编号 $d$ 是一个层级图表。
  2. 字符串 $d$ $(c_1)$ $(c_2)$ $\dots$ $(c_n)$ 是一个层级图表,其中 $d$ 是一个部门编号,$c_1, c_2, \dots, c_n$ 是层级图表。

情况 2 表示部门 $d$ 负责管理位于层级 $c_1, c_2, \dots, c_n$ 顶部的部门。每行输入最多包含 $100\,000$ 个部门,且没有任何部门负责管理超过 $100$ 个其他部门。所有部门编号均为 $1$ 到 $1\,000\,000$ 之间的整数。我们称情况 1 描述的层级图表领导深度为 1,情况 2 描述的层级图表领导深度等于 $1$ 加上层级图表 $c_1, c_2, \dots, c_n$ 的最大领导深度。输入的领导深度最多为 $1\,000$。在左括号或右括号的两侧可能有任意数量的空格。

输出格式

如果两张层级图表相似,则输出 Yes,否则输出 No

样例

样例输入 1

11 (10) (12 (13) (17) (28))
11 (12 (17) (28) (13)) (10)

样例输出 1

Yes

样例输入 2

11 ( 10 ) ( 12 )
11(10(12))

样例输出 2

No

样例输入 3

11 (10) (12)
11 (10) (13)

样例输出 3

No

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.