#PQJ3343x17204. QOJ 3343_17204

    ID: 2920 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2026深搜

QOJ 3343_17204

第二试渡船(ferry) IOI2026 中国国家队选拔 渡船(ferry) 【题目描述】 海上散布着n 座岛屿,岛屿之间共有m 条双向航线。第i (1 ≤i ≤m) 条航线连接 岛屿ui 与vi,并且在这条航线上有一艘渡船往返运行。 每艘渡船有一个初始停泊位置。对于第i (1 ≤i ≤m) 条航线上的渡船, • 若wi = 0,则渡船初始停泊在岛屿ui; • 若wi = 1,则你可以任意决定渡船初始停泊在岛屿ui 或岛屿vi。 现在有k 位旅人,第j (1 ≤j ≤k) 位旅人初始位于岛屿sj,需要前往岛屿tj。旅 人只能通过渡船移动。具体地,每次移动会选择一位旅人j (1 ≤j ≤k) 与一条航线 i (1 ≤i ≤m),满足旅人j 与航线i 上的渡船当前位于同一座岛屿,然后旅人将会登上 渡船,与渡船一同移动到航线i 另一端的岛屿。例如,若旅人j 与航线i 上的渡船均位 于岛屿ui,则移动后旅人与渡船均会抵达岛屿vi,反之亦然。 你需要判断,是否可以通过一系列旅人的移动,使得所有旅人均能到达各自的目的 地。若存在,你还需要给出一组具体的移动方案。 【实现细节】 .选.手.不.需.要,.也.不.应.该.实.现main .函.数。 选手需要确保提交的程序包含头文件ferry.h,即在程序开头加入以下代码: #include "ferry.h" 1 选手需要在提交的程序源文件中实现以下函数: void ferry(int n, int m, int k, std::vector u, 1 std::vector v, std::vector w, std::vector s, std::vector t); • n, m, k 分别表示岛屿的数量、航线的数量与旅人的数量。 • 对于0 ≤i < m,ui, vi 分别表示第i + 1 条航线连接的两座岛屿,wi 表示该航线 上的渡船的初始停泊位置是否确定,具体见【题目描述】。 • 对于0 ≤j < k,sj, tj 分别表示第j + 1 位旅人初始位于的岛屿与目的地岛屿。 • 对于每个测试点,该函数会被交互库调用.恰.好.一.次。 选手可以通过调用以下函数报告是否可以通过一系列旅人的移动,使得所有旅人均 能到达各自的目的地: void report(bool o); 1 • 若o 为true,则表示可以通过一系列旅人的移动,使得所有旅人均能到达各自 的目的地;若o 为false,则表示不可以。 第2 页 共14 页 第二试渡船(ferry) IOI2026 中国国家队选拔 • 选手需要保证交互库调用ferry 时,.恰.好.调.用.了.一.次.该.函.数。 选手可以通过调用以下函数进行一次移动: void move(int j, int i); 1 • j, i 分别表示选择的旅人与航线的编号,具体含义如【题目描述】中所示。选手 需要保证1 ≤j ≤k,1 ≤i ≤m,且旅人j 与航线i 上的渡船当前位于同一座岛 屿。特别地,若航线i 上的渡船的初始停泊位置还未确定,且旅人j 位于航线i 连接的其中一座岛屿,则航线i 上的渡船的初始停泊位置直接被确定为旅人j 所 在的岛屿。 • 选手需要保证交互库每次调用ferry 时,调用该函数的次数不超过106,且所 有该函数的调用.均.在.调.用report .函.数.之.后,且report .函.数.的.返.回.值.必.须.为 true。 .注.意:.在.任.何.情.况.下,.交.互.库.运.行.所.需.时.间.均.不.会.超.过0.1 .秒,.所.用.内.存.为.固.定.大 .小,.且.均.不.超.过64 MiB。 【测试程序方式】 .试.题.目.录.下.的grader.cpp .是.交.互.库.参.考.实.现,.最.终.测.试.时.所.用.的.交.互.库.实.现.与.该 .参.考.实.现.有.所.不.同,.因.此.选.手.的.解.法.不.应.该.依.赖.交.互.库.实.现。 选手可以在本题目录下使用如下命令编译得到可执行程序: g++ grader.cpp ferry.cpp ‐o ferry ‐std=gnu++14 ‐O2 ‐pipe ‐static ‐s 1 对于编译得到的可执行程序: • 可执行文件将从.标.准.输.入读入以下格式的数据: – 输入的第一行包含三个正整数n, m, k,分别表示岛屿的数量、航线的数量 与旅人的数量。 – 输入的第i + 1 (1 ≤i ≤m) 行包含三个非负整数ui, vi, wi,分别表示第i 条 航线连接的两座岛屿与该航线上的渡船的初始停泊位置是否确定,具体见 【题目描述】。 – 输入的第n + 2 行包含k 个正整数s1, . . . , sk,分别表示每位旅人初始位于 的岛屿。 – 输入的第n + 3 行包含k 个正整数t1, . . . , tk,分别表示每位旅人的目的地岛 屿。 • 可执行文件将输出以下格式的数据至.标.准.输.出: – 输出的第一行包含一个字符串Yes 或No,表示是否可以通过一系列旅人的 移动,使得所有旅人均能到达各自的目的地。 – 若可以,则 第3 页 共14 页 第二试渡船(ferry) IOI2026 中国国家队选拔 ∗输出的第二行包含一个非负整数c,表示移动次数; ∗输出的第l + 2 (1 ≤i ≤c) 行包含两个正整数j, i,分别表示第l 次移动 选择的旅人与航线的编号。 【样例1 输入】 4 5 2 1 1 2 1 2 3 1 0 3 3 2 0 4 2 4 1 5 4 3 0 6 1 4 7 3 2 8 【样例1 输出】 Yes 1 4 2 2 5 3 2 3 4 1 1 5 1 3 6 【样例1 解释】 • 初始时,旅人1 位于岛屿1,旅人2 位于岛屿4; • 第一次移动后,旅人2 与航线5 上的渡船一同移动到岛屿3; • 第二次移动后,旅人2 与航线3 上的渡船一同移动到岛屿2; • 第三次移动时,航线1 上的渡船的初始停泊位置被确定为岛屿1,移动后旅人1 与航线1 上的渡船一同移动到岛屿2; • 第四次移动后,旅人1 与航线3 上的渡船一同移动到岛屿3。 【附加文件说明】 在附加文件中:

  1. grader.cpp 是提供的交互库参考实现。
  2. ferry.h 是头文件,选手不用关心具体内容。 第4 页 共14 页 第二试渡船(ferry) IOI2026 中国国家队选拔
  3. template_ferry.cpp 是提供的示例代码,选手可参考并实现自己的代码。 【子任务】 对于所有测试数据,均有: • 2 ≤n ≤2, 000,1 ≤m ≤104,1 ≤k ≤102; • 对于所有1 ≤i ≤m,均有1 ≤ui, vi ≤n,ui̸ = vi,wi ∈{0, 1}; • 对于所有1 ≤i ≤k,均有1 ≤si, ti ≤n。 子任务编号 分值 特殊性质 1 6 k = 1 k = n,且s1, . . . , sn 与t1, . . . , tn 均为1 ∼n 的排列 2 7 对于所有1 ≤i ≤m,均有wi = 0 3 11 对于所有1 ≤i ≤m,均有wi = 1 4 9 存在一个1 ∼k 的排列p,满足对于所有1 ≤i ≤k,均有si = tpi 5 29 n ≤100,m ≤200,k ≤60 6 26 无 7 12 【评分方式】 .注.意: • 选手不应当通过非法方式获取交互库的内部信息,如直接与标准输入、输出流进 行交互。此类行为将被视为作弊; .最.终.的.评.测.交.互.库.与.样.例.交.互.库.的.实.现.不.同。 • .本.题.首.先.会.受.到.和.传.统.题.相.同.的.限.制,例如编译错误会导致整道题目得0 分,运行 时错误、超过时间限制、超过空间限制等会导致相应测试点得0 分等。选手只能在程序 中访问自己定义的变量以及交互库给出的变量,尝试访问其他地址空间将可能导致编译 错误或运行错误。 每次调用ferry 函数时,若report 函数或move 函数调用不合法,或move 函数 调用次数超过106,则相应测试点得0 分。 在上述条件基础上: • 对于每个测试点,若report 函数返回值正确,则可以获得40% 的分数;在此基 础上,若report 返回值为false,或ferry 函数返回时所有旅人均到达对应的 目的地岛屿,则可以获得满分。 第5 页 共14 页