Educational Codeforces Round 15 E. Analysis of Pathes in Functional Graph （倍增RMQ）
Educational Codeforces Round 15 E. Analysis of Pathes in Functional Graph （倍增RMQ）
E. Analysis of Pathes in Functional Graph
time limit per test
memory limit per test
input
output
You are given a functional graph. It is a directed graph, in which from each vertex goes exactly one arc. The vertices are numerated from 0 to n - 1.
Graph is given as the array f0, f1, ..., fn - 1, where fi — the number of vertex to which goes the only arc from the vertex i. Besides you are given array with weights of the arcs w0, w1, ..., wn - 1, where wi — the arc weight from i to fi.
The graph from the first sample test.
Also you are given the integer k (the length of the path) and you need to find for each vertex two numbers si and mi, where:
si— the sum of the weights of all arcs of the path with length equals tokwhich starts from the vertexi;mi— the minimal weight from all arcs on the path with lengthkwhich starts from the vertexi.
The length of the path is the number of arcs on this path.
Input
The first line contains two integers n, k (1 ≤ n ≤ 105, 1 ≤ k ≤ 1010). The second line contains the sequence f0, f1, ..., fn - 1 (0 ≤ fi < n) and the third — the sequence w0, w1, ..., wn - 1 (0 ≤ wi ≤ 108).
Output
Print n lines, the pair of integers si, mi
Examples
input
7 31 2 3 4 3 2 66 3 1 4 2 2 3
output
10 18 17 110 28 27 19 3
input
4 40 1 2 30 1 2 3
output
0 04 18 212 3
input
5 31 2 3 4 04 1 2 14 3
output
7 117 119 221 38 1
题意：给你一个图，图中n个点n个边(有向)，每个边长度为1，上面有一个数字。给你一个k，对每个点询问距离为k的路径中的所有数的和，以及所有路径中最小的数。n<=100000 K<=10^10。
题解：因为k很大啊，很明显要倍增，直接用RMQ就可以了。（倍增RMQ）
代码：
#pragma comment(linker, "/STACK:102400000,102400000")#include
相关文章
发表评论
暂时没有评论，来抢沙发吧~