UOJ Logo Universal Online Judge

UOJ

#365. 【JOISC2017】City

附件下载 统计

JOI 王国有很多城市,城市之间由双向道路连接。道路系统满足以下条件:

  • 城市被标号为 $0$ 到 $N - 1$(其中 $N$ 为城市总数)。
  • 有且仅有 $N - 1$ 条道路,且从任一城市出发都能经过若干条道路抵达其它所有城市。
  • 从 $0$ 到其它任何城市都只需经过不超过 $18$ 条道路。

在 JOI 王国,每天都会有很多人从城市 $0$ 向其它城市出发。由于很多人有两个目的地,他们时常会问以下问题:对于两个不同城市 $X, Y$,以下哪个条件满足?

(0) 要抵达 $X$ 就必须经过 $Y$;

(1) 要抵达 $Y$ 就必须经过 $X$;

(2) 以上两者均不满足。

容易发现上述情形中 (0), (1), (2) 总是恰有一条满足。特别地,当 $Y = 0$ 时我们认为满足的条件是 $(0)$;$X = 0$ 的情况类似。

事实上,其它国家的道路系统往往也满足 1~3。因此,JOI 王国的人们希望开发以下两个程序从而解决一般性的问题:

  • (程序 1) 给定城市个数 $N$ 和所有道路信息,该程序会给每个城市确定一个 $[0, 2^{60} - 1]$ 内的编码。

  • (程序 2) 给定城市 $X$ 和 $Y$ 对应编码,该程序会回答对应的问题(即返回三种情况之一)。

注意运行程序 2 时并不会直接给出 $N$ 和道路信息。

请实现以上两个程序。

实现细节

本题仅支持 C/C++ 语言。

你需要提交两个文件。

第一个文件名应为 Encoder.cEncoder.cpp。该文件为你对程序 1 的实现。请包含头文件 Encoder.h

你需要实现以下函数:

  • void Encode(int N, int A[], int B[])
    • 每组测试数据中,该函数会被调用恰好一次。
    • 参数 $\texttt{N}$ 表示城市个数。
    • 数组 $\texttt{A[]}$ 和 $\texttt{B[]}$ 的长度均为 $N - 1$,表示对每个 $i \in [0, N - 2]$,城市 $\texttt{A[i]}$ 和 $\texttt{B[i]}$ 之间有一条道路。

你可以调用以下函数:

  • void Code(int city, long long code)
    • 该函数用于给城市指定编码。
    • 你需要保证 $\texttt{city} \in [0, N - 1]$,否则会被判为 Wrong Answer[1]。你还需要保证每次调用时 $\texttt{city}$ 的取值不同,否则会被判为 Wrong Answer[2]
    • 你还需要保证 $\texttt{code} \in [0, 2^{60} - 1]$,否则会被判为 Wrong Answer[3]

你的程序应当调用 $\texttt{Code}$ 恰好 $N$ 次,否则会被判为 Wrong Answer[4]

若以上过程中你的程序被判为 Wrong Answer,它会被立即终止。

第二个文件名应为 Device.cDevice.cpp。该文件为你对程序 1 的实现。请包含头文件 Device.h

你需要实现以下函数:

  • void InitDevice()

    • 每组测试数据中,该函数会被调用恰好一次(且是在 $\texttt{Answer}$ 被调用之前)。
  • int Answer(long long S, long long T)

    • 该函数中,你需要回答询问。
    • 参数 $\texttt{S}$ 和 $\texttt{T}$ 为 $X$ 和 $Y$ 在 $\texttt{Encode}$ 中被给予的编号。
    • 若 $0$ 到 $X$ 的任何路径都经过 $Y$,该函数应返回 $0$。
    • 若 $0$ 到 $Y$ 的任何路径都经过 $X$,该函数应返回 $1$。
    • 否则,该函数应返回 $2$。
    • 若 $\texttt{Answer}$ 的返回值不在 $[0, 2]$ 内,你会被判为 Wrong Answer[5];答案错误则会被判为 Wrong Answer[6]

评分方式

评分方式如下:

若你的程序被判定为 Wrong Answer,它会被立即终止。

(1) 函数 $\texttt{Encode}$ 会被调用恰好一次。

(2) 函数 $\texttt{InitDevice}$ 会被调用恰好一次。

(3) 对每个测试点,程序 2 会被进行 $Q$ 次询问。对于第 $j (j \in [1, Q])$ 次询问,$\texttt{Answer}(S_j, T_j)$ 会被调用,其中 $S_j$ 和 $T_j$ 分别为城市 $X_j$ 和 $Y_j$ 的编号。

(4) 上述过程结束后,你的程序会被判为正确。

注意事项

  • 运行时间和空间是对于以上整个过程计算的。注意 $\texttt{Answer}$ 函数会被调用 $Q$ 次。

  • 你的程序不应当在上述过程中返回 Wrong AnswerRuntime Error

  • 你的程序可以调用自己实现的内部函数或使用全局变量。被提交的程序会被使用同一 grader 编译成单个可执行文件。全局变量和内部函数应用 static 定义以避免重名。

  • 评分时两个程序可被视为独立的部分,因而不能共用全局变量。

  • 你的程序不应当向标准输入输出或其他文件进行任何读写操作。

测试程序方式

「附加文件」中提供了 Encoder.hDevice.hgrader.cgrader.cpp 四个文件。若你编写的程序名称为 Encoder/Device.cEncoder/Device.cpp,请运行以下命令来编译:

  • C 语言 gcc -std=c11 -O2 -o grader grader.c Encoder.c Device.c -lm

  • C++ 语言 g++ -std=c++14 -O2 -o grader grader.cpp Encoder.cpp Device.cpp

当命令成功时,会产生一个可执行文件 grader

注意实际评测时的程序与下发的样例评测程序并不相同。实际的 grader 实现将通过标准输入输出进行通信。

样例评测程序输入格式

样例评测程序将从标准输入读入以下数据。

  • 第 $1$ 行两个整数 $N, Q$,表示城市和询问个数。

  • 接下来的 $N - 1$ 行中,第 $i + 1(0 \leq i \leq N - 2)$ 行两个整数 $A_i, B_i$,表示一条道路。

  • 接下来的 $Q$ 行中,第 $j$($1 \leq j \leq Q$)行包含两个空格分隔的整数 $X_j, Y_j, E_j$,表示进行一次关于 $X_j$ 和 $Y_j$ 的询问,正确答案为 $E_j$。

样例评测程序输出格式

样例评测程序将向标准输出输出以下信息。

  • 判为正确时,输出形如 Accepted: max_code=123456 的信息;

  • 运行过程中被判为错误时,以 Wrong Answer [x] 的格式报告并退出。

程序执行过程中违反了多种限制时,只会报告其中的一种。

数据范围与提示

  • $2 \leq N \leq 250 000$。

  • $1 \leq Q \leq 250 000$。

  • $0 \leq A_i \leq N - 1 (0 \leq i \leq N - 2)$。

  • $0 \leq B_i \leq N - 1 (0 \leq i \leq N - 2)$。

  • $A_i, B_i (0 \leq i \leq N - 2)$。

  • 从城市 $0$ 出发经过不超过 $18$ 条道路可抵达任何城市。

  • $0 \leq X_j \leq N - 1 (1 \leq j \leq Q)$。

  • $0 \leq Y_j \leq N - 1 (1 \leq j \leq Q)$。

  • $X_j\neq Y_j (1 \leq j \leq Q)$。

子任务 1(8 分)

  • $N \leq 10$。

子任务 2(92 分)

无特殊限制。该子任务的得分按以下方式计算:

  • 记 $L$ 为所有城市的最大编码。
    • $L \geq 2^{38}$ 时记 $0$ 分。
    • $2^{36} \leq L \leq 2^{38} - 1$ 时记 $10$ 分。
    • $2^{35} \leq L \leq 2^{36} - 1$ 时记 $14$ 分。
    • $2^{34} \leq L \leq 2^{35} - 1$ 时记 $22$ 分。
    • $2^{28} \leq L \leq 2^{34} - 1$ 时记 $\lfloor 372 - 10 \log_2(L + 1) \rfloor$ 分(其中 $\lfloor x \rfloor$ 为下取整)。
    • $L \leq 2^{28} - 1$ 时记 $92$ 分。
    • 注意当 $L \geq 2^{38}$ 时,评测系统有可能显示 Accepted: 0 pointsWrong Answer