为什么数组还要再开大一半?
  • 板块学术版
  • 楼主xxgirlxx
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/6/8 22:11
  • 上次更新2024/6/9 09:23:35
查看原帖
为什么数组还要再开大一半?
1059074
xxgirlxx楼主2024/6/8 22:11

这是我的 E 题代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200010],cnt[200010],vis[200010],ans;
vector<int>edge[200010];
void dfs1(int x,int sum[],int to[]){
	to[x]=1;
	for(int i=0;i<edge[x].size();i++){
		if(to[edge[x][i]]==1)continue;
		sum[edge[x][i]]=sum[x]+1;
		dfs1(edge[x][i],sum,to);
	}
}
void dfs2(int x){
	vis[x]=1;
	for(int i=0;i<edge[x].size();i++){
		if(vis[edge[x][i]]==1)continue;
		cnt[edge[x][i]]=cnt[x]+1;
		dfs2(edge[x][i]);
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		edge[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		if(a[i]==i){
			cnt[i]=1;
			vis[i]=1;
			continue;
		}
		int sum[n+10],to[n+10];
		sum[i]=1;
		sum[a[i]]=0;
		dfs1(i,sum,to);
		if(sum[a[i]]!=0){
			int num=a[i],res=1;
			while(num!=i){
				res++;
				num=a[num];
			}
			num=a[i];
			while(num!=i){
				cnt[num]=res;
				vis[num]=1;
				num=a[num];
			}
			cnt[i]=res;
			vis[i]=1;
		}
	}
	
	for(int i=1;i<=n;i++){
		if(cnt[i]!=0){
			dfs2(i);
		}
	}
	for(int i=1;i<=n;i++){
		ans+=cnt[i];
	}
//	for(int i=1;i<=n;i++)cout<<cnt[i]<<" ";
	cout<<ans;
	
	return 0;
}
/*
*/

然而,它会 WA 一个点,题目实际上也只有 2×1052 \times 10^5,但是如果我开 3×1053 \times 10^5,它就 AC 了。请问一下各位神犇大佬:这是为什么?

2024/6/8 22:11
加载中...