记录编号	582222	评测结果	AAAAAAAAAA
题目名称	3714.Analysis of Pathes in Functional Graph	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.736 s
提交时间	2023-09-06 18:28:56	内存使用	109.88 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 45;
typedef long long ll;
const ll INF = 1e9;
int n,a[maxn];
ll k,c[maxn],f[maxn][maxm],tot[maxn][maxm],sum[maxn][maxm];
ll solvetot(int i,ll k) {
    if(!k)return 0;
    int x = 0;
    for(;(1ll << x) <= k;++ x);-- x;
    return tot[i][x] + solvetot(f[i][x] , k ^ (1ll << x));
}
ll solvemin(int i,ll k) {
    if(!k)return INF;
    int x = 0;
    for(;(1ll << x) <= k;++ x);-- x;
    return min(sum[i][x] , solvemin(f[i][x] , k ^ (1ll << x)));
}
int main() {
    freopen("pathsjump.in", "r", stdin);
    freopen("pathsjump.out", "w", stdout);
    scanf("%d%lld",&n,&k);
    for(int i = 1;i <= n;++ i)scanf("%d",&a[i]),f[i][0] = a[i];
    for(int i = 1;i <= n;++ i)scanf("%lld",&c[i]),sum[i][0] = tot[i][0] = c[i];
    for(int t = 1;t <= 40;++ t) {
        for(int i = 1;i <= n;++ i) {
            f[i][t] = f[f[i][t - 1]][t - 1];
        }
    }
    for(int t = 1;t <= 40;++ t) {
        for(int i = 1;i <= n;++ i) {
            sum[i][t] = min(sum[i][t - 1] , sum[f[i][t - 1]][t - 1]);
            tot[i][t] = tot[i][t - 1] + tot[f[i][t - 1]][t - 1];
        }
    }
    for(int i = 1;i <= n;++ i) {
        printf("%lld %lld\n",solvetot(i , k),solvemin(i , k));
    }
    return 0;
}