33OJ
登录 注册

#P7068. [NWRRC 2014] Instruction

[NWRRC 2014] Instruction

题目描述

英格丽德是一家大型火车站的站长,除其他职责外,还负责将火车开到正确的站台。车站有一个入口,有许多道岔将列车引导至其他道岔和站台。

每个道岔有一条入站轨道和两条出站轨道,站台有一条入站轨道,车站入口有一条出站轨道。每个出站磁道连接到一个入站磁道,反之亦然。每个道岔和站台都可以从车站入口到达。

月台有一个铁路死胡同,你可以假设火车到达月台后立即从月台上消失。

每天早上,英格丽德都会查看时间表,并编写切换指令:何时以及切换哪个开关。她希望将此过程自动化以节省大量时间。

输入格式

输入文件的第一行包含一个整数 nn —— 站点上交换机和平台的总数

以下 nn 行的第 ii 行描述了具有索引 ii 的交换机或平台。说明以字符 p 开头表示平台,以字符 s 开头表示交换机。下一个数字 qiq_i表示入站轨道连接到的道岔的编号,如果连接到车站入口,则表示 0(0≤qi≤i)0(0\le q_i\le i)。

平台说明还包含一个唯一的小写英文字母 —— 平台标识符。

列车在两个相连的道岔或道岔与站台之间移动只需一分钟。早上,每一个道岔都会以一种方式进行切换,列车将通过连接到道岔/站台的两条出站轨道中编号较低的一条。 输入文件的下一行包含一个整数 m(0≤m≤1000)m(0\le m\le 1000) —— 时刻表上的列车数量。

以下 mm 行中的每一行都包含整数 ai(0≤ai≤10000;ai>ai−1)a_i(0\le a_i \le 10000;a_i>a_{i-1}) —— 列车到达车站入口的时间(以分钟为单位),以及字母 pip_i —— 列车目的站台的标识符。

输出格式

在第一行输出整数 cc——开关切换指令中的命令数。

对于每个命令,输出两个整数 sis_i和 ti(1≤si≤n;0≤ti≤109)t_i(1\le s_i \le n;0 \le t_i \le 10^9) —— 开关的编号和切换开关的时间。假设开关在分钟之间切换 ti−1t_i-1 和 tt。

按非递减时间顺序输出命令。命令的数量不应超过 100000100000。

7
s 0
s 1
s 1
p 2 a
p 2 b
p 3 c
p 3 d
5
0 a
1 c
3 b
4 a
5 d

6
1 2
1 4
2 4
2 6
1 6
3 7

5
s 0
p 1 y
s 1
p 3 z
p 3 x
3
7 y
8 y
15 y

0

3
s 0
p 1 y
p 1 z
3
7 y
8 y
10 y

5
1 1
1 2
1 2
1 3
1 200