记录编号	582268	评测结果	AAAAAAAAAA
题目名称	Analysis of Pathes in Functional Graph	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	4.530 s
提交时间	2023-09-07 16:56:15	内存使用	11.08 MiB

#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N = 1e5+10;
ll n,k,cnt,tot,mi;
struct made{
    ll ed,ver;
}e[N];
ll a[N],fa[N],ans[N],ss,su,d[N];
ll v[N],kk;
void work(ll x,ll end){
    if(x == end)return;
    d[tot]++;
    ss += e[x].ed;
    fa[x] = tot;
    work(e[x].ver,end);
}
void sou(ll x,ll s){
    if(v[x]){
        if(v[x] == s){
           ss = e[x].ed;
           tot++;
           d[tot] = 1;
           fa[x] = tot;
           work(e[x].ver,x);
           ans[tot] = ss;
        }
        return;
    }
    v[x] = cnt;
    sou(e[x].ver,s);
}
void work_(ll x,ll end){
    if(x == end)return;
    mi = min(e[x].ed,mi);
    work_(e[x].ver,end);
}
void dfs(ll x){
    if(fa[x]){
        su += ans[fa[x]] * ll(kk / d[fa[x]]);
        if(kk >= d[fa[x]]){
            mi = min(e[x].ed,mi);
            work_(e[x].ver,x);
        }
        kk -= (kk / d[fa[x]]) * d[fa[x]];
    }
    if(kk == 0)return;
    mi = min(mi,e[x].ed);
    su += e[x].ed;
    kk--;
    dfs(e[x].ver);
}
int main() {
    freopen("pathsjump.in","r",stdin);
    freopen("pathsjump.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    for(int i = 1;i <= n;i++)scanf("%lld",&a[i]);
    for(int i = 1;i <= n;i++){
        ll x;
        scanf("%lld",&x);
        e[i].ver = a[i],e[i].ed = x;
    }
    for(int i = 1;i <= n;i++){
        if(!v[i]){
            cnt++;
            sou(i,cnt);
        }
    }
//    for(int i = 1;i <= n;i++)printf("%d ",d[i]);
//    printf("\n");
    for(int i = 1;i <= n;i++){
        kk = k,su = 0,mi = INT_MAX;
        dfs(i);
        printf("%lld %lld\n",su,mi);
    }
    
    return 0;
    
}