这是一道交互题。
最终,UOI 主席亲自向大家宣布了大D米 AK UOI 的消息,会场响起了经久不衰的掌声与欢呼声。
然而天下没有不散的宴席,终于到了大家需要各自坐航天飞机回去的疏散日。此时,你的电话铃声响起,原来是两只外星老鼠舒克和贝塔打来的,他们的银河系航空公司在疏散日这天遭遇了难以解决的客流高峰。
银河系的星球近似地分布在了一张平面上。舒克和贝塔的航空公司控制了
舒克和贝塔的航空公司掌握着这
现在由于航空需求的瞬间增长,绝大部分飞机行程已被排满,仅有两架飞机处于空闲状态。初始它们分别停在
对于每条航线,舒克和贝塔给出了一个正整数价值。为了尽可能早地到达对应机场缓解客流压力,舒克和贝塔将某架空闲飞机从机场
需要注意的是,每一次客流紧张事件发生时,舒克和贝塔可以任选两架飞机中的一架去到对应机场,而不需要比较它们需要经过的航线的价值和。特别地,即使当前客流紧张事件发生的机场停靠了一架处于空闲状态的飞机,舒克和贝塔也可以选择调度另一架飞机到当前机场。
在满足了这些条件之后,舒克和贝塔最后的想法是在这些客流紧张事件中小赚一笔。具体地,舒克和贝塔希望在依次解决
为了保护商业机密,舒克和贝塔并不能为你直接提供航线地图和每条航线的价值。幸运的是,他们允许你在他们的航线地图存储系统上进行至多
任务
本题仅支持 C++。
你必须引用 airline.h
头文件。
你需要实现下面的过程:
long long solve(int n, int x, int y, int q, std::vector<int> P, int L)
其中
你可以调用以下过程和交互库进行交互:
long long distance(int p, int q)
其中
评测方式
样例评测库将读入如下格式的输入数据:
第一行包括五个正整数
接下来
接下来一行
在最终测试中,航线集合以及每条航线的价值是确定的,不会因为你的询问而改变。
样例评测库将输出如下格式的输出数据:
如果你的程序正确地完成了交互,评测库将会输出两行,第一行一个整数表示 solve
函数的返回结果,第二行一个整数表示 distance
函数调用的次数。如果你的程序没有正确完成交互,则会输出对应的交互错误信息。
在输入数据满足题目条件、询问次数不超过题目限制的情况下,保证最终评测时使用的交互库不会使用超过
样例一
input
4 4 1 3 2000000 1 2 96 2 3 27 3 4 33 4 1 96 2 4 79 2 4 4 4
output
189
explanation
该组样例的航线地图如下图所示,其中每条航线上对应的数字表示其价值。初始两架空闲飞机分别停在
一个满足题目条件且经过的所有航线的价值和最大的方案如下:
- 第一次客流紧张事件发生在
号机场。将停留在 号机场的飞机调度至 号机场,此时调度路线会是 ,价值和为 ; - 第二次客流紧张事件发生在
号机场。将停留在 号机场的飞机调度至 号机场,此时调度路线会是 ,价值和为 ; - 第三次客流紧张事件依然发生在
号机场。将之前停留在 号机场、经过第一次客流紧张事件后调度到 号机场的飞机调度至 号机场,此时调度路线会是 ,价值和为 ; - 第四次客流紧张事件仍然发生在
号机场。此时两架飞机都停靠在 号机场,调度其中任意一架都不会经过额外的航线,价值为 。
对于该方案需要注意的是:
- 每一次客流紧张事件结束后,解决该次客流紧张事件的飞机会停靠在客流紧张事件发生的机场,而不是初始机场,如第一次客流紧张事件后原来停留在
号机场的飞机停留在了 号机场。 - 方案中将某架飞机调度到当前的客流紧张机场时一定会选择经过的航线价值和最小的路径。例如第三次客流紧张事件,将
号机场的飞机调度到 号机场的调度路线改为 是不合法的。 - 方案中不能存在将某一架飞机调度到当前的非客流紧张机场的调度。
- 第三次客流紧张事件发生时,发生事件的
号机场已经有一架空闲飞机。此时将另一架飞机调度到 号机场是合法的; - 同时,将一架空闲飞机调度到其所在的机场是合法的,如第四次客流紧张事件的调度。此时经过的航线价值和为
;
该方案经过的航线价值和为 solve
函数的返回值即评测库的输出应该为
样例二
见附加文件中 ex_airline2.in
与 ex_airline2.out
,该组样例满足子任务 2 的性质。
样例三
见附加文件中 ex_airline3.in
与 ex_airline3.out
,该组样例满足子任务 4 的性质。
样例四
见附加文件中 ex_airline4.in
与 ex_airline4.out
,该组样例满足子任务 5 的性质。
数据范围
对于
温馨提示:你可以使用
子任务编号 | 特殊性质 | 分值 | ||
---|---|---|---|---|
A | ||||
无 | ||||
A | ||||
B | ||||
无 |
子任务 1 和 4 的特殊性质为:
- 航线集合随机生成,生成方式为:对一个凸多边形,如果点数不超过 3 则退出;否则随机两个不相邻的顶点,在它们之间连边,并对该边分割的两个凸多边形递归处理。
- 每条航线的价值在
内独立均匀随机。 次客流紧张事件发生的机场编号在 内独立均匀随机。
子任务 5 的特殊性质为:
; 次客流紧张事件发生的机场编号按照时间顺序单调不降,即solve
函数传入的P
数组单调不降。
注意在使用 Hack 时需要保证
时间限制:
空间限制: