#P3587. 猴子挖矿

    ID: 2788 传统题 1000ms 512MiB 尝试: 7 已通过: 3 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS动态规划线性 DP滚动数组图论Kosaraju 算法状态扩展图枚举与搜索广度优先搜索组合数学补集计数数论最小公倍数模逆元中国剩余定理折半枚举两半结果排序匹配排序与序列处理相向双指针CF3100By佚名提供

猴子挖矿

猴子挖矿

题目描述

cxm 最近在玩一个叫做猴子挖矿的游戏。

这个游戏由两个玩家参加。开始时地图中会随机生成一些矿点,玩家需要操作自己的猴子探索未知的道路,抢占对方的矿点。已经占领的矿点每回合会产生 11 单位的矿石。玩家用手中的矿石可以购买路灯、护盾、传送等道具。最终获得矿石较多的玩家获胜。

cxm 对这个游戏进行了一些改动。现在游戏在一个有 nn 个点,mm 条边的有向图上进行,为了方便起见,cxm 用 11 到 nn 的整数来表示地图中的点。

玩家只有一个,但他拥有无限数量的猴子。游戏最开始时,所有的猴子都在第 11 个点。从第 00 回合到第 11 回合起,每只猴子在相邻两回合之间都必须沿一条有向边移动。不同猴子可以走不同的路线。只有沿自环移动时,猴子才可能在移动后仍位于原点;无路可走的猴子在下一回合消失。

游戏开始时为第 00 回合。从第 ss 回合开始,到第 tt 回合结束(包括第 ss 回合和 tt 回合),每回合每个点都会出产 11 单位的矿石。如果在该回合玩家有至少一只猴子在出产矿石的点,那么玩家将获得这个矿石,否则这个矿石会在下一回合消失。

现在 cxm 想知道,在图中每个点分别最多能收集到多少单位矿石。

输入格式

标准输入。

输入第一行包含四个整数 n,m,s,tn,m,s,t,分别表示有向图中点的个数,边的个数,开始出产的时间和结束出产的时间。
接下来 mm 行,每行包含两个 11 到 nn 的整数 x,yx,y,用空格隔开,表示有一条从第 xx 个点到第 yy 个点的有向边。

输出格式

标准输出。

输出 nn 行,每行包含一个整数,按照 11 到 nn 的顺序依次表示在每个点可以获得的矿石个数。

样例

5 7 0 19
1 3
1 4
1 5
3 2
2 1
3 4
5 5
7
6
7
13
19

数据规模与约定

对于 100%100\% 的数据,保证 0<n≤1000<n\le 100,0<m≤3000<m\le 300,0≤s≤t≤10150\le s\le t\le 10^{15}。

样例说明

原样例的有向图及回合表

猴群从点 11 出发,可以沿 1→3→2→11\to3\to2\to1 循环。每逢有猴子到达点 11,可以分别派出猴子沿 1→41\to4 和 1→3→41\to3\to4 走,在相邻的两个回合收集点 44 的矿石。走 1→51\to5 到达点 55 后,可以不断沿 5→55\to5 移动,从第 11 回合起收集点 55 所有的矿石。

点 可以收集矿石的回合
1 0、3、6、9、12、15、18
2 2、5、8、11、14、17
3 1、4、7、10、13、16、19
4 1、2、4、5、7、8、10、11、13、14、16、17、19
5 1 至 19