P4768 [NOI2018]归程

    • 1.2K通过
    • 4.5K提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 可持久化 并查集 最短路 NOI系列 2018 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 4000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    本题因为一些原因只能评测16组数据。

    剩下的四组数据:https://www.luogu.org/problemnew/show/U31655

    题目描述

    本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 $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 {0,1}$ 是一个会在下面被用到的系数,$S$ 表示的是可能的最高水位线。

    接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0; p_0$ 描述一天:
    这一天的出发节点为$v = (v_0 + K \times \mathrm{lastans} - 1) \bmod n + 1$。
    这一天的水位线为$p = (p_0 + K \times \mathrm{lastans}) \bmod (S + 1)$。
    其中 lastans 表示上一天的答案(最小步行总路程)。特别地,我们规定第 $1$ 天时 lastans = 0。 在这里,我们保证$1 \leq v_0 \leq n,0 \leq p_0 \leq S$ 。

    对于输入中的每一行,如果该行包含多个数,则用单个空格将它们隔开。

    输出格式:

    依次输出各组数据的答案。对于每组数据:

    • 输出 $Q$ 行每行一个整数,依次表示每天的最小步行总路程。

    输入输出样例

    输入样例#1: 复制
    1
    4 3
    1 2 50 1
    2 3 100 2
    3 4 50 1
    5 0 2
    3 0
    2 1
    4 1
    3 1
    3 2
    输出样例#1: 复制
    0
    50
    200
    50
    150
    输入样例#2: 复制
    1
    5 5
    1 2 1 2
    2 3 1 2
    4 3 1 2
    5 3 1 2
    1 5 2 1
    4 1 3
    5 1
    5 2
    2 0
    4 0
    输出样例#2: 复制
    0
    2
    3
    1

    说明

    【样例1 解释】 第一天没有降水,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 一条链 不保证
    $\leq 1500$ $=n-1$ $2000$ 8 一条链 不保证
    $\leq 1500$ $=n-1$ $2000$ 9 一条链 不保证
    $\leq 200000$ $=n-1$ $100000$ 10 一棵树 不保证
    $\leq 200000$ $=n-1$ $100000$ 11 一棵树 不保证
    $\leq 200000$ $\leq 400000$ $100000$ 12 不保证 不保证
    $\leq 200000$ $\leq 400000$ $100000$ 13 不保证 不保证
    $\leq 200000$ $\leq 400000$ $100000$ 14 不保证 不保证
    $\leq 1500$ $\leq 4000$ $2000$ 15 不保证 不保证
    $\leq 1500$ $\leq 4000$ $2000$ 16 不保证 不保证
    $\leq 200000$ $\leq 400000$ $100000$ 17 不保证 不保证
    $\leq 200000$ $\leq 400000$ $100000$ 18 不保证 不保证
    $\leq 200000$ $\leq 400000$ $400000$ 19 不保证 不保证
    $\leq 200000$ $\leq 400000$ $400000$ 20 不保证 不保证
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。