#B. 括号路径(bracket)

    Type: Default File IO: bracket 2000ms 256MiB

括号路径(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.

巡给你 nn 个点 mm 条边的无向图,每个结点上有一个字符 ( 或者 )

巡给你 qq 次查询,每次查询给出 x,yx,y,你需要判断是否存在一条从 xxyy 的路径(不需要保证是简单路径)满足将路径上的点上的字符顺次写下来得到的字符串是合法括号串。

合法括号串的定义:

  • 空字符串是合法括号串
  • A,BA,B 是合法括号串,则 ABAB 是合法括号串
  • AA 是合法括号串,则 (A)(A) 是合法括号串
  • 除此之外的其他字符串均不是合法括号串

()(()()) 是合法括号串,(()())( 不是合法括号串。

输入格式

第一行三个整数 n,m,qn,m,q

第二行一个只包含 () 的长度为 nn 的字符串表示结点 1n1\dots n 上的字符。

下面 mm 行,每行两个整数 u,vu,v 表示图上的一条边。

下面 qq 行,每行两个整数 x,yx,y

输出格式

一个长度为 qq 的 01 串,第 ii 个字符表示第 ii 次询问的答案,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

【样例解释】

其中 1,2,31,2,3 号点的字符是 (4,54,5 号点的字符是 )

  • 121\to 2:显然,合法括号串不可能以 ( 结尾。
  • 343\to 4:路径 343\to 4 表示的字符串是 ()
  • 141\to 4:路径 1324541\to 3\to 2\to 4\to 5\to 4 表示的字符串是 ((()))
  • 151\to 5:路径 12451\to 2\to 4\to 5 表示的字符串是 (())
  • 252\to 5:路径 23452\to 3\to 4\to 5 表示的字符串是 (())

样例 2

见下发 bracket2.in/ans\textit{bracket2.in/ans}

该样例满足测试点 22 的性质。

数据范围

对所有数据,保证 n,q5×105n,q\leq 5\times 10^5m2nm\leq 2n

不保证图联通,不保证无重边自环。

测试点编号 nn\leq qq\leq 特殊性质
11 1010
22 10310^3
33 5×1055\times 10^5 5×1055\times 10^5 图为一棵树
44 1010
55 5×1055\times 10^5

NOIP 2024 模拟赛(三)

Not Attended
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