CF704E Iron Man

发表于 分类于 ， ， 阅读次数：

题意：给出一棵 个节点的树，每条边的长度是 。

有 个鸡贼，第 个鸡贼在时刻 出现在节点 ，以 的速度沿简单路径向节点 移动。

若两个鸡贼在某个时刻重合，则会发生爆炸。（路径左闭右闭，端点处也算）

问最早何时发生爆炸，或指出不会爆炸。

，时限 。

首先考虑一条链的情况，上树可以树剖一下，对每条重链的答案取 。

然后就是问有若干个点在数轴上移动，问最早发生两个点重合的时间。

按 “位置 ，时间 ” 两维画出图像，一个点的移动轨迹是一条线段，我们的目的是求出这些线段 最小的交点。

这些线段不具有任何特殊性质，看起来较难处理，但是我们发现：在第一个交点出现之前,所有的线段都是不交的。对付一些不交的线段，可以扫描线解决。

按照时间从小到大的顺序，从左端点加入线段，右端点删除。由于不交，所有线段之间的 坐标相对顺序是不变的。

由此又能得到一个结论：只需要考虑每条线段到前后相邻的两条线段的交点。

具体实现时，可以使用 std::set 来维护线段,重载运算符，全局一个 表示当前时间，代入线段中使用函数值来比较。

每次加入线段时，与其两侧的线段求交点，更新答案。

注意，第一个求出的交点不一定是是最靠左的，需要一直求下去，直到当前的 已经大于求出的交点为止。

复杂度 。

实现细节：

  • 将路径视作（时间，深度）的函数，便于思考。

  • 我们需要删除元素，而 set 的 find 只基于 < 符号，也就是说判断 a==b 会使用 !(a<b||b<a) 。

    所以我们重载 < 时，当函数值相近，要比较编号。

  • 两线段求交点要讨论重合，平行，正常三种情况。

  • 把线段的端点向两边扩一点，以更好地模拟闭区间。

  • 对于一条重链上线段较少的情况，可以暴力减小常数。

  • 不仅插入时要计算与两个邻居的贡献，删除时也要计算一对新的邻居的贡献。

  • 当目前的 时马上 break 以免触发 set 的 UB。