专栏文章

题解：P14467 [COCI 2025/2026 #1] 扔球 / Krugomet

IInnitTimmer_
P14467题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minazgfw
此快照首次捕获于
2025/12/01 23:27
3 个月前
此快照最后确认于
2025/12/01 23:27
3 个月前
查看原文
首先看到这个题，一眼想到的就是模拟，但是后来发现 kk 太大了，完全不能模拟，所以考虑倍增。
设 fai,jfa_{i,j} 表示编号为 ii 的人传 2j2^j 次球后会到谁手里，仿照倍增求 LCA 的思路，显然有 fai,j=fafai,j−1,j−1fa_{i,j}=fa_{fa{i,j-1},j-1}。
那我们就可以预处理出这个东西，然后直接给这个人加上答案即可，时间复杂度 O(n×log⁡k)O(n\times \log k)。
CPP
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=1e5+10;
int _=1,n,k,ans=0,a[N],cnt[N],fa[N][31];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),k=reads();
		for(int i=1;i<=n;i++) a[i]=reads();
		for(int i=1;i<=n;i++) fa[i][0]=reads();
		for(int j=1;j<=30;j++){
			for(int i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1];
		}
		for(int i=1;i<=n;i++){
			int u=i,p=k;
			for(int j=30;j>=0;j--){
				int x=(1<<j);
				if(p>=x) u=fa[u][j],p-=x;
			}
			cnt[u]+=a[i];
		}for(int i=1;i<=n;i++) ans=max(ans,cnt[i]);
		printf("%lld\n",ans);
		for(int i=1;i<=n;i++){
			if(cnt[i]==ans) printf("%lld ",i);
		}
	}return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...