记录编号	582336	评测结果	AAAAAAAAAA
题目名称	Analysis of Pathes in Functional Graph	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	4.135 s
提交时间	2023-09-09 17:18:11	内存使用	120.18 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; 
typedef long long ll;
const int maxn=100010,maxm=50;
int n;
long long k,f[maxn][maxm],s[maxn][maxm],mi[maxn][maxm];
long long jis(int x,long long k2)
{
    long long ans=0;
    for(int i=40;i>=0;i--)
    {
        if((1ll<<i)<=k2)
        {
            ans+=s[x][i];
            x=f[x][i];
            k2=k2^(1<<i);
        }
    }
    return ans;
}
long long jimi(int x,long long k2)
{
    long long ans=0x3f3f3f3f3f3f3f3f;
    for(int i=40;i>=0;i--)
    {
        if((1ll<<i)<=k2)
        {
            ans=min(ans,mi[x][i]);
            x=f[x][i];
            k2=k2^(1<<i);
        }
    }
    return ans;
}
int main()
{
    freopen("pathsjump.in","r",stdin);
    freopen("pathsjump.out","w",stdout);
    memset(mi,0x3f,sizeof(mi));
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&f[i][0]);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&s[i][0]);
        mi[i][0]=s[i][0];
    }
    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++)
        {
            s[i][t]=s[i][t-1]+s[f[i][t-1]][t-1];
            mi[i][t]=min(mi[i][t-1],mi[f[i][t-1]][t-1]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%lld %lld\n",jis(i,k),jimi(i,k)); 
    }
    return 0;
}