记录编号	599848	评测结果	AAAAAAAAAA
题目名称	Analysis of Pathes in Functional Graph	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	2.400 s
提交时间	2025-03-29 16:22:01	内存使用	54.97 MiB

#include <cstdio>
typedef long long ll;

template <typename T>
T min(T x, T y) {
	return x < y ? x : y;
}

const int MAXN = 1e5 + 10;

int n; ll k;
int f[MAXN][35]; // f[i][j] : The point that point i step 2^j reaches
ll g[MAXN][35]; // g[i][j] : The sum of weigh that point i step 2^j collects
int h[MAXN][35]; // h[i][j] : The minimum weigh that point i step 2^j can get

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", &f[i][0]);
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &g[i][0]);
		h[i][0] = (int)g[i][0];
	}
	for (int j = 1; j <= 34; ++j) {
		for (int i = 1; i <= n; ++i) {
			f[i][j] = f[f[i][j - 1]][j - 1];
			g[i][j] = g[i][j - 1] + g[f[i][j - 1]][j - 1];
			h[i][j] = min(h[i][j - 1], h[f[i][j - 1]][j - 1]);
		}
	}
	for (int i = 1; i <= n; ++i) {
		ll ans = 0;
		int now = i, mini = 0x7fffffff;
		for (int j = 0; j <= 34; ++j) {
			if ((k >> j) & 1) {
				ans += g[now][j];
				mini = min(mini, h[now][j]);
				now = f[now][j];
			}
		}
		printf("%lld %d\n", ans, mini);
	}
	return 0;
}