UOJ Logo Universal Online Judge

UOJ

Attachment Statistics

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

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

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

三十年后,他离开了这片大地,前往更广阔的世界,去寻找这种力量的根源。离开跳蚤国前,他留下了一段话,并把绝大多数力量封印在了魔法阵中:“这种神奇的力量是属于 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 打开。

Please upload the file(s) named as road1.out, road2.out, road3.out, road4.out, road5.out, road6.out, road7.out, road8.out, road9.out. We will unzip any ZIP file that you upload.


Or upload file(s) via the following form: