UOJ Logo Universal Online Judge

UOJ

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

附件下载 统计

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

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

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

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

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

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

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

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

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

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

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

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

输入格式

本题为提交答案题。

所有输入数据 road1.in ~ road9.in 见数据下载。

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

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

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

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

接下来 m 行,每行两个数 u,v,表示一条有向边 uv1u,vn

输出格式

针对给定的输入数据 road1.in ~ road9.in 你需要分别给出输出 road1.out ~ road9.out

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

样例输入

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

样例输出

3

样例解释

最长路径为 123,对应字符串为 "aba",是一个回文串,长度为 3

评分方式

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

如何检验你的输出

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

对于一个测试点,设你的答案为 x。如果 ((x+23333)mod25+9999)mod7 的值与 ans 相等,则你的答案可能是正确的,否则你的答案一定是错误的。

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

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

测试点分值与评分参数

测试点编号 分值 ans
176
285
383
4102
5111
6135
793
8142
9200

数据下载

百度盘下载链接: 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 压缩包,我们会为你自动解压。


或者通过如下表单上传: