题解

思路

最先完成的任务一定是入度为零的源点。固定最早时刻后，沿编号顺序按依赖计算每个任务的最早绝对完成时刻。

做法

先令所有源点在第零天完成，顺序计算每个任务最早的不小于全部前驱时刻、且模 $k$ 等于 $h_i$ 的时刻。把源点按 $h$ 排序，依次尝试每个不同的源点小时作为区间左端。

左端越过某组源点时，把这些源点推迟一整天。由它们向后传播：一个点的时刻只可能增加 $k$，且整个扫描过程中至多增加一次，所以所有传播总计为 $O(n+m)$。维护当前最大完成时刻，即可更新答案。

无依赖时问题等价于在长度为 $k$ 的圆周上覆盖所有小时，答案是 $k$ 减去最大环形空隙。小规模可对每个源点小时重新计算完整最早时刻。

复杂度

每组时间复杂度 $O((n+m)\log n)$，空间复杂度 $O(n+m)$。