括号路径(bracket)
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
巡给你 个点 条边的无向图,每个结点上有一个字符 (
或者 )
。
巡给你 次查询,每次查询给出 ,你需要判断是否存在一条从 到 的路径(不需要保证是简单路径)满足将路径上的点上的字符顺次写下来得到的字符串是合法括号串。
合法括号串的定义:
- 空字符串是合法括号串
- 若 是合法括号串,则 是合法括号串
- 若 是合法括号串,则 是合法括号串
- 除此之外的其他字符串均不是合法括号串
如 ()
、(()())
是合法括号串,(()
、())(
不是合法括号串。
输入格式
第一行三个整数 。
第二行一个只包含 (
和 )
的长度为 的字符串表示结点 上的字符。
下面 行,每行两个整数 表示图上的一条边。
下面 行,每行两个整数 。
输出格式
一个长度为 的 01 串,第 个字符表示第 次询问的答案,1 表示存在这样的路径,0 表示不存在这样的路径。
样例 1
【样例输入】
5 6 5
((())
1 2
1 3
2 3
3 4
4 5
2 4
1 2
3 4
1 4
1 5
2 5
【样例输出】
01111
【样例解释】
其中 号点的字符是 (
, 号点的字符是 )
。
- :显然,合法括号串不可能以
(
结尾。 - :路径 表示的字符串是
()
。 - :路径 表示的字符串是
((()))
。 - :路径 表示的字符串是
(())
。 - :路径 表示的字符串是
(())
。
样例 2
见下发 。
该样例满足测试点 的性质。
数据范围
对所有数据,保证 ,。
不保证图联通,不保证无重边自环。
测试点编号 | 特殊性质 | ||
---|---|---|---|
无 | |||
图为一棵树 | |||
无 | |||
NOIP 2024 模拟赛(三)
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2024-8-8 8:00
- End at
- 2024-8-8 12:00
- Duration
- 4 hour(s)
- Host
- Partic.
- 38