【UER #1】跳蚤OS - 题目 - Universal Online Judge

跳蚤OS 是跳蚤国自主研发的功能强大的操作系统。

跳蚤OS的文件系统与普通的文件系统类似，是个文件夹套文件夹的结构。文件系统根目录称为“ $/$ ”。我们可以用文件路径来表明文件所在的位置，比如“ $/flea/uoj$ ”表示根目录下的 $flea$ 文件夹下的 $uoj$ 文件。

跳蚤OS的文件系统中。快捷方式是一种特殊的文件夹，点开该快捷方式相当于打开该快捷方式指向的文件夹。

比如，如果有一个快捷方式 “ $/etc/abc$ ”，该快捷方式指向 “ $/flea/def$ ”这个文件夹，那么一旦访问“ $/etc/abc$ ”就相当于访问“ $/flea/def$ ”。

这一天，跳蚤国王正在使用跳蚤OS。初始时文件系统为空，只有根目录。他每次会进行如下操作：

首先，随便写出两个文件路径 $s$ 和 $t$ 。
接着，如果位置 $t$ 处不存在文件，则在该处创建一个空文件夹。
最后，跳蚤国王保证 $s$ 这个位置没有文件，于是在 $s$ 处创建一个快捷方式指向 $t$ 。如果 $t$ 是个快捷方式，那么 $s$ 将指向 $t$ 所指向的文件夹。

上文所说的“创建”在父级目录不存在的时候要一并创建其父级目录。比如，假设文件系统里只有 “ $/v$ ” 这个文件夹，那么现在我创建 “ $/v/flea/king/qaq$ ” 就会在文件系统中新增三个文件夹：“ $/v/flea$ ”, “ $/v/flea/king$ ”, “ $/v/flea/king/qaq$ ”。

跳蚤国王进行了 $n$ 次这样的操作后，开始不断问他的助手伏特：现在我如果在 $p$ 这个路径处创建一个文件夹（如果已存在则不创建），那么这个文件夹的真实路径是什么？

于是伏特只好向你求助了，请你帮一帮他吧！请参照样例来更清晰地理解题意。

输入格式

第一行两个正整数 $n, m$ ，表示跳蚤国王进行了 $n$ 个操作，提了 $m$ 个问题。

接下来 $n$ 行每行两个用空格隔开的字符串 $s, t$ ，表示跳蚤国王的一次操作。

接下来 $m$ 行每行一个字符串 $p$ 表示跳蚤国王的一个询问。

保证所有的 $s, t, p$ 都是合法的文件路径。即，文件夹名一定是由小写英文字母组成的非空字符串，路径名一定形如“ $/xxx/xxx/xxx/.../xxx$ ”这样子。保证当路径不为根目录“ $/$ ”时，路径不以“ $/$ ”结尾。

输出格式

对于跳蚤国王的每个询问输出真实路径。

样例一

input

6 5
/root /
/duliu /picks
/vfk /vfleaking
/orz/orz/orz /duliu
/otl /duliu/duliu
/vfk/sb /vfleaking
/vfk/sb/nothing/nothing
/orz
/orz/orz/orz
/qaq
/otl

output

/vfleaking/nothing/nothing
/orz
/picks
/qaq
/picks/duliu

explanation

创建的快捷方式分别为：

$/root \to /$
$/duliu \to /picks$
$/vfk \to /vfleaking$
$/orz/orz/orz \to /picks$
$/otl \to /picks/duliu$
$/vfleaking/sb \to /vfleaking$

样例二

input

2 3
/ba/la /
/w/o/w /w
/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la
/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba/la/ba
/w/o/w/o/w/o/w/o

output

/
/ba
/w/o

样例三

见样例数据下载

限制与约定

测试点编号	$n$	$m$	其他
1	$\leq 200$	$\leq 10$	保证单个字符串长度不会超过 $40$
2
3
4	$\leq 20000$		保证每个输入的路径字符串中仅包含一个“ $/$ ”且位于字符串开头。保证单个字符串长度不超过 $15$ 。
5
6
7	$\leq 20000$
8
9
10

对于所有数据，输入中路径字符串总长度不会超过 $5 \times 10^{5}$ 。

时间限制： $1 s$

空间限制： $256 MB$

为了防止有些同学看晕了，我还是再罗嗦几句。下面的路径名都是非法的：

$/orz/$
$/orz//otl$
$/233$ （注意，只能含有小写英文字母）

下面的路径名都是合法的：

$/$
$/orz/otl/oorrzz/oottll$
$/a$

下载

样例数据下载

Universal Online Judge

UOJ

#13. 【UER #1】跳蚤OS

输入格式

输出格式

样例一

input

output

explanation

样例二

input

output

样例三

限制与约定

下载