【NOI2018】归程 排行榜
时间限制: 4 s
空间限制: 524288 KB
题目背景
本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。
魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图(节点的编号从 $1$ 至 $n$)。我们依次用 $l,a$ 描述一条边的长度、海拔。
作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。
我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。
题目描述
Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。
Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天,每一天 Yazid 都会告诉你他的出发点 $v$ ,以及当天的水位线 $p$。
每一天,Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
需要特殊说明的是,第二天车会被重置,这意味着:
车会在新的出发点被准备好。
Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。
本题的部分测试点将强制在线,具体细节请见【输入格式】和【子任务】。
输入格式
从标准输入读入数据。
单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$,表示数据的组数。接下来依次描述每组数据,对于每组数据:
第一行 $2$ 个非负整数 $n,m$,分别表示节点数、边数。
接下来 $m$ 行,每行 $4$ 个正整数 $u,v,l,a$,描述一条连接节点 $u,v$ 的、长度为 $l$、海拔为 $a$ 的边。
- 在这里,我们保证 $1\leq u,v\leq n$。
接下来一行 $3$ 个非负数 $Q,K,S$,其中 $Q$ 表示总天数,$K\in\left\{0,1\right\}$ 是一个会在下面被用到的系数,$S$ 表示的是可能的最高水位线。
接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0,p_0$ 描述一天:
这一天的出发节点为 $v=\left(v_0+K\times lastans-1\right)\bmod n+1$。
这一天的水位线为 $p=\left(p_0+K\times lastans\right)\bmod \left(S+1\right)$。
其中 $lastans$ 表示上一天的答案(最小步行总路程)。特别地,我们规定第 $1$ 天时 $lastans=0$。
在这里,我们保证 $1\leq v_0\leq n$,$0\leq p_0\leq S$。
对于输入中的每一行,如果该行包含多个数,则用单个空格将它们隔开。
输出格式
输出到标准输出。
依次输出各组数据的答案。对于每组数据:
- 输出 $Q$ 行每行一个整数,依次表示每天的最小步行总路程。
样例一
输入
输出
解释
第一天没有降水,Yazid 可以坐车直接回到家中。
第二天、第三天、第四天的积水情况相同,均为连接 $1,2$ 号节点的边、连接 $3,4$ 号点的边有积水。
对于第二天,Yazid 从 $2$ 号点出发坐车只能去往 $3$ 号节点,对回家没有帮助。因此 Yazid 只能纯靠徒步回家。
对于第三天,从 $4$ 号节点出发的唯一一条边是有积水的,车也就变得无用了。Yazid 只能纯靠徒步回家。
对于第四天,Yazid 可以坐车先到达 $2$ 号节点,再步行回家。
第五天所有的边都积水了,因此 Yazid 只能纯靠徒步回家。
样例二
输入
输出
解释
本组数据强制在线。
第一天的答案是 $0$,因此第二天的 $v=\left( 5+0-1\right)\bmod 5+1=5$,$p=\left(2+0\right)\bmod\left(3+1\right)=2$。
第二天的答案是 $2$,因此第三天的 $v=\left( 2+2-1\right)\bmod 5+1=4$,$p=\left(0+2\right)\bmod\left(3+1\right)=2$。
第三天的答案是 $3$,因此第四天的 $v=\left( 4+3-1\right)\bmod 5+1=2$,$p=\left(0+3\right)\bmod\left(3+1\right)=3$。
子任务
所有测试点均保证 $T\leq 3$,所有测试点中的所有数据均满足如下限制:
$n\leq 2\times 10^5$,$m\leq 4\times 10^5$,$Q\leq 4\times 10^5$,$K\in\left\{0,1\right\}$,$1\leq S\leq 10^9$。
对于所有边:$l\leq 10^4$,$a\leq 10^9$。
任意两点之间都直接或间接通过边相连。
为了方便你快速理解,我们在表格中使用了一些简单易懂的表述。在此,我们对这些内容作形式化的说明:
图形态:对于表格中该项为“一棵树”或“一条链”的测试点,保证 $m=n-1$。除此之外,这两类测试点分别满足如下限制:
一棵树:保证输入的图是一棵树,即保证边不会构成回路。
一条链:保证所有边满足 $u+1=v$。
海拔:对于表格中该项为“一种”的测试点,保证对于所有边有 $a=1$。
强制在线:对于表格中该项为“是”的测试点,保证 $K=1$;如果该项为“否”,则有 $K=0$。
对于所有测试点,如果上述对应项为“不保证”,则对该项内容不作任何保证。
$n$ | $m$ | $Q=$ | 测试点 | 图形态 | 海拔 | 强制在线 |
---|---|---|---|---|---|---|
$\leq 1$ | $\leq 0$ | $0$ | 1 | 不保证 | 一种 | 否 |
$\leq 6$ | $\leq 10$ | $10$ | 2 | |||
$\leq 50$ | $\leq 150$ | $100$ | 3 | |||
$\leq 100$ | $\leq 300$ | $200$ | 4 | |||
$\leq 1500$ | $\leq 4000$ | $2000$ | 5 | |||
$\leq 200000$ | $\leq 400000$ | $100000$ | 6 | |||
$\leq 1500$ | $=n-1$ | $2000$ | 7 | 一条链 | 不保证 | |
8 | ||||||
9 | ||||||
$\leq 200000$ | $100000$ | 10 | 一棵树 | |||
11 | 是 | |||||
$\leq 400000$ | 12 | 不保证 | 否 | |||
13 | ||||||
14 | ||||||
$\leq 1500$ | $\leq 4000$ | $2000$ | 15 | 是 | ||
16 | ||||||
$\leq 200000$ | $\leq 400000$ | $100000$ | 17 | |||
18 | ||||||
$400000$ | 19 | |||||
20 |
为了优化你的阅读体验,我们在表格中把测试点的编号放在了中间,请注意这一点。
题目来源
NOI 2018 Day 1
关于接口中的数组初值说明(最后更新:2023年2月6日)
若题目要求实现函数接口,且该函数中存在仅用于输出的数组(如 void solve(int n, const int *in, int *out)
中的 out
),那么除非另外说明,否则该数组在程序启动时的初值为 0
。
关于标准输出的说明(最后更新:2018年10月23日)
标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。
如果你的程序要进行大量输出,请考虑这一点。
关于提交的说明
你提交的代码将会被公开,所有人都可见。如果这不是你所期望的,或者如果想要删除已提交的代码,请联系管理员。
Judge Duck Online | 评测鸭在线
Server Time: 2024-09-08 09:04:58 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用