UOJ Logo Universal Online Judge

UOJ

#695. 【候选队互测2022】毛估估就行

附件下载 统计

有时候,做人不能太斤斤计较。社会上讲究一个让步和妥协,大家都得给自己和对方留一些余地。所以有时候不必太追求精确,毛估估就行。

俗话说得好,“退一步海阔天空”,本题的出题人也想和大家和平相处。本着给选手多送分的原则,这道题你不必求出精确解,毛估估求一下就行啦!如果你的答案和精确值差不多,出题人会假装没看出来区别然后给你满分的!

那么接下来描述这个送分题的题面:有一张 $n$ 个点的无向无权连通图,$q$ 次查询两点之间的最短路长度。但正如前面所说的,只要你与答案差不超过 $1$,即如果最短路长度是 $d$,输出 $d-1,d,d+1$ 之一时,出题人都会假装你算的是对的。

这时候大家可能会问了,这不是普及组题目吗?我刚学 OI 的时候就做过了!所以出题人决定加大题目的数据范围,但这下出题人都不会做了。不过,你会吗?

输入格式

为了减小输入量,本题对输入进行了压缩

第一行两个正整数 $n,q$,表示图的点数和询问次数。

接下来 $n-1$ 行,第 $i$ 行为一个长度为 $\lceil \frac{i}{4} \rceil$ 的字符串,仅包含 '0' ~ '9''A' ~ 'F'。这里,字符 '0'~'9' 依次对应整数 $0\sim 9$,'A'~'F' 依次对应整数 $10\sim 15$。

对 $\forall 1\leq j\leq i$,$G$ 中边 $(j,i+1)$ 存在当且仅当该字符串第 $\lceil \frac{j}{4} \rceil$ 个字符所对应整数的二进制表示下从低往高第 $(j-1) \bmod 4$ 位为 $1$,注意若 $i \bmod 4\neq 0$,则最后一个字符二进制表示下没有定义的位一定为 $0$。

接下来 $q$ 行,每行两个正整数 $x,y(1\leq x,y\leq n)$,表示一次询问。

输出格式

$q$ 行,每行一个整数,表示毛估估求出的答案。如果精确答案为 $d$,输出 $d-1,d,d+1$ 均算作正确答案。

样例一

input

4 3
1
1
5
1 2
2 3
3 4

output

1
2
1

explanation

边集为 $(1,2),(1,3),(1,4),(3,4)$。

注意这里的样例输出给的是精确答案,很多其他输出也会被认为是正确答案,如 $1,3,0$。

数据范围

对于所有数据,保证 $2\leq n\leq 8000,1\leq q\leq 10^6$。

子任务编号 $n\leq$ $q\leq$ 特殊性质 分值
$1$ $500$ $10^6$ $10$
$2$ $2500$ $20$
$3$ $5000$ A $20$
$4$ $8000$ $8000$ $20$
$5$ $8000$ $10^6$ $30$

特殊性质 A:每条边 $(i,j)(1\leq i < j\leq n)$ 以 $\frac 12$ 概率出现。

时间限制:$3\texttt{s}$

空间限制:$1\texttt{GB}$

提示

请选手相信自己算法的常数与评测机的效率