UOJ Logo Universal Online Judge

UOJ

#313. 【UNR #2】解开尘封的仪式

附件下载 统计

本题是一道提交答案题,由于输入文件较大,请及早下载数据。

一切要从远古时期说起……

那时还没有跳蚤国,世界一片混乱。一位伟大的跳蚤先知,在一次意外的偶遇中,获得了一种神秘的力量。他使用这种强大的力量,统一了那片大地,建立了最初的跳蚤国。

三十年后,他离开了这片大地,前往更广阔的世界,去寻找这种力量的根源。离开跳蚤国前,他留下了一段话,并把绝大多数力量封印在了魔法阵中:“这种神奇的力量是属于 OI 的力量,想要掌握这种力量,必须要按照仪式才能解开封印。”

千年后的跳蚤国。又是一场战争,跳蚤国受到了来自蛐蛐国、跳晚国等的围攻,敌方的势力过于强大,很难阻挡。

跳蚤国王想起了先知离开前说过的话,决定用仪式解开尘封了千年的 OI 的力量,挽救跳蚤国于危亡之中。

跳蚤国王打开了魔法阵,发现这个魔法阵是九个魔法阵的叠加,他决定一个个破解魔法阵。

按照远古的仪式,跳蚤国王需要按照魔法阵的形状,将 $n$ 只跳蚤排成一个阵法的形状。这个阵法可以抽象成一个有向图。每个跳蚤可以从一些跳蚤那里接收力量,也可以把力量传递给另外一些跳蚤。有 $m$ 个这样的魔法通道,可以把一个跳蚤身上的力量单向传输到另外一个跳蚤身上。

这种属于 OI 的力量太过强大,所以没有人能掌控的时候,这种属于 OI 的力量是不稳定的。如果出现了一只跳蚤的力量经过某些魔法通道传递到了他本身,那么这个魔法阵就会因为不稳定而自爆,所以这个魔法阵是不存在环的。

每个跳蚤的身上有一个字符,而一条路径对应的就是一个字符串。先知的预言里曾经说过,只有回文串才能提供魔力,打开这个阵法;而回文串越长,自然激发出来的力量就越强。

为了最大程度的解开封印的力量,跳蚤国王希望从魔法阵中选出一些跳蚤组成一条路径,使该路径对应的字符串是最长的回文串。

因为某些魔法阵力量的残缺,有的魔法阵还规定了路径的起点或终点。

输入格式

本题为提交答案题。

所有输入数据 $\texttt{road1.in}$ ~ $\texttt{road9.in}$ 见数据下载。

对于每组数据,输入文件格式如下:

第一行两个数 $n$,$m$,表示这个图的点数和边数。

下一行两个参数 $S,T$。$S$ 表示你要找的回文路径的起点,$T$ 表示你要找的回文路径的终点。当 $S=0$ 表示起点可以为任意节点;同样,当 $T=0$ 表示终点可以为任意点。

接下来 $n$ 行每行一个字符,给出每个点上的字符。

接下来 $m$ 行,每行两个数 $u,v$,表示一条有向边 $u \rightarrow v$($1 \leq u,v \leq n$)

输出格式

针对给定的输入数据 $\texttt{road1.in}$ ~ $\texttt{road9.in}$ 你需要分别给出输出 $\texttt{road1.out}$ ~ $\texttt{road9.out}$。

对于每组数据,给出一个数作为答案,即最长的回文路径长度。

样例输入

3 3
1 3
a
b
a
1 2
1 3
2 3

样例输出

3

样例解释

最长路径为 $1 \rightarrow 2 \rightarrow 3$,对应字符串为 "aba",是一个回文串,长度为 $3$。

评分方式

答案为一个整数,如果正确则该测试点满分。

如何检验你的输出

我们将给出每个答案的检验值 $\mathrm{ans}$,你可以使用该值对你的结果进行校验。

对于一个测试点,设你的答案为 $x$。如果 $ ( ( x + 23333 ) \bmod 25 + 9999 ) \bmod 7$ 的值与 $\mathrm{ans}$ 相等,则你的答案可能是正确的,否则你的答案一定是错误的。

最终测试时,你的答案与标准答案完全一致才能得分。

比赛时,一个测试点只要提交了非空的文件,则算该测试点满分。

测试点分值与评分参数

测试点编号 分值 $\mathrm{ans}$值
17$6$
28$5$
38$3$
410$2$
511$1$
613$5$
79$3$
814$2$
920$0$

数据下载

百度盘下载链接: https://pan.baidu.com/s/1dEZ4ryp 密码: tupm

对于每个输入文件,我们提供了 windows 换行符结尾和 linux 换行符结尾两种格式。

由于 5 号点和 9 号点大小特别大,我们提供了两种下载方式:你可以选择直接下载压缩包慢慢等,也可以在文件夹中选择测试点一个个下载到本地。

注意,由于本题输入文件较大,请选择方便查看大文件的文本编辑器观察数据特点。linux 下推荐 vim 或 Emacs 等,windows 下推荐 notepad++。或者另一个选择是使用一些 IDE 比如 GUIDE 打开。

请上传你要提交的文件,并命名为 road1.out, road2.out, road3.out, road4.out, road5.out, road6.out, road7.out, road8.out, road9.out。如果你提交了 zip 压缩包,我们会为你自动解压。


或者通过如下表单上传: