UOJ Logo Universal Online Judge

UOJ

#509. 【JOISC2020】迷路的猫

Statistics

Anthony 是一只生活在 JOI 市的蚂蚁。JOI 市共有被划分为 $N$ 个町,编号为 $0$ 到 $N-1$。Anthony 居住在 $0$ 号町。总共有 $M$ 条路,编号为 $0$ 到 $M-1$。第 $i$ 条路连接编号为 $U_i$ 和 $V_i$ 的町 ($U_i \neq V_i$),每条路是双向的。保证不存在两条连接两个相同的町的道路,同时每个点可以直接或间接互相到达。

Catherine 是一只猫,也是 Anthony 的好朋友。她打算游览 JOI 市,但是她并不知道关于路的信息,所以经常迷路。于是,Anthony 打算事先在每条道路上都作上标记。标记共有 $A$ 种,编号为 $0$ 到 $A-1$。

Catherine 现在到达了 JOI 市。当她不在 $0$ 号町时,她会做如下事情:

  • 对于每种标记,她会统计当前所在的町连出去的道路中,除了她上一次走来的道路(若存在)之外,这种标记共出现了多少次。

之后她会选择一条路去行动。注意除了上一次走来路,她仅能通过路上的标记来分辨其余的道路。她想尽量快地到达 $0$ 号町。更准确地说,若起点至 $0$ 号町最少需要经过 $d$ 条道路,那么她希望在经过不超过 $d+B$ 条边后就能到达 $0$ 号町。

你需要编写程序模拟 Anthony 摆放路标和 Catherine 探索 JOI 城的过程。

交互细节

你需要提交两个程序。

第一个程序为Anthony.cpp,它会模拟Anthony的摆放过程。需要包含头文件Anthony.h

  • std::vector<int> Mark(int N, int M, int A, int B, std::vector<int> U, std::vector<int> V)

    该程序会恰好在开始时调用一次。

    • 数字 $N,M,A,B$ 含义同题面。
    • U,V存储着所有的边,$\texttt{U[i]}$ 和 $\texttt{V[i]}$ 表示第$i$条路连接的街道 $U_i$ 和 $V_i$。

    选手需要返回一个长度为 $M$ 的数组 $x$,第 $i$ 个元素 $x_i$ 代表在第 $i$ 条道路上的路标编号。

    若 $x$ 长度不为 $M$,测评结果为 "Wrong Answer [1]"。若不满足 $0 \le x_i \le A-1$,测评结果为 "Wrong Answer [2]"。

第二个程序为Catherine.cpp,它会模拟Catherine的探索过程。需要包含头文件Catherine.h

  • void Init(int A, int B)

    该程序会恰好在开始时调用一次。

    • 数字 $A,B$ 含义同题面。
  • int Move(std::vector<int> y)

    该程序会在每次Catherine到达一个不是0的街道时调用。

    • $y$ 是一个长度为$A$的数组,元素 $y_j$ 代表着所有与当前街道相连且不为她上一次走过的路(若存在)的路上标记 $j$ 的出现次数。
    • 你需要返回一个整数 $z$,表示选择走的标记。需要满足 $-1 \le z \le A-1$。若不满足 $-1 \le z \le A-1$,测评结果为 "Wrong Answer [3]"。若 $z=-1$,表示Catherine原路返回,此时若Catherine未进行过任何操作,测评结果为 "Wrong Answer [4]"。若 $0 \le z \le A-1$,表示 Catherine 选择一条标记为 $z$ 的边经过,此时若 $y_z=0$,测评结果为 "Wrong Answer [5]"。

    注意如果有多条可以选择的边,grader不一定会随机选择一条合法的出现行动。

    如果 Catherine 未能在 $D+b$ 步内到达街道0,测评结果为 "Wrong Answer [6]"。

注意事项

选手程序可能会运用若干全局变量和子程序。为了防止多个文件变量重名或子程序重名带来的编译错误,请将所有全局变量和子程序定义在一个没有名字的 namespace 里。

如果在程序里使用 printf/scanf/cout/cin,会直接导致 Wrong Answer 或者 Runtime Error。

最终测评时会将 Anthony 和 Catherine 的程序独立编译,因此不能共享全局变量。

编译与运行

grader.cpp, Anthony.cpp,Catherine.cpp,Anthony.h,Catherine.h放在同一文件夹下,在终端内运行如下命令

g++ -O2 -o grader grader.cpp Anthony.cpp Catherine.cpp

编译成功时会得到一个可执行文件grader

可执行文件从标准输入种读入以下内容:

第一行五个数字 $N,M,A,B,S$。其中$S$表示起点。

接下来$M$行,每行两个数字 $U_i,V_i$,表示一条道路。

可执行文件回想标准输出流输出以下内容。

若程序运行时产生错误 [1] 至 [5],则会输出形如 "Wrong Answer [1]" 的错误信息。

否则如果未在 $N+B$ 步内到达街道1,输出 "Wrong Answer; Number of moves > N + B".

否则按照 "Number of moves = 4" 的格式输出信息。

数据范围

  • 子任务1 ($2$分):$A=4, B=0, M=N-1$。
  • 子任务2 ($2$分):$A=4, B=0$。
  • 子任务3 ($2$分):$A=3, B=0, M=N-1$。
  • 子任务4 ($9$分):$A=3, B=0$。
  • 子任务5 ($5$分):$A=2, B=2N, M=N-1, 6 \le N \le 500$。
  • 子任务6 ($71$分):$A=2, B=12, M=N-1$。
  • 子任务7 ($9$分):$A=2, B=6, M=N-1$。

对于所有测试数据,满足 $2 \le N \le 20000,1 \le M \le 20000,1 \le S < N$。

保证图联通且无重边无自环。

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

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

关于 UOJ 上该题的测评方式

由于传这道题的时候 vfk 想起了自己学过的密码学,于是决定加点密码学玩玩 233

UOJ 测评该题时会用基于 mt19937_64 的流加密算法对输入输出进行加密,并用基于 SHA256 的 HMAC 做数字签名。私钥是随机的,每次测评直接编译进交互库。为了防止交互库被 include 后套出私钥,交互库的文件名也是随机的。

vfk 想知道这种情况下交互库还能不能被 hack?(期待)

下载

样例及测评库下载