进士厚仁,如果你40分TLE
查看原帖
进士厚仁,如果你40分TLE
1395172
Nlu5E5Bl楼主2025/2/8 16:59

统计请用减法,合一个减一,不要单独统计,会被卡

……
	for(int i=0;i<n;i++){
		if(isdel[i]) continue;
		for(int j=0;j<e[i].size();j++){
			if(isdel[e[i][j]]) continue;
			int fi=find(i),fj=find(e[i][j]);
			if(fi!=fj){
				fa[fj]=fi;
			}
		}
	}
	memset(cnt,0x00,sizeof(cnt));
	for(int i=0;i<n;i++){
		if(isdel[i]) continue;
		int fi=find(i);
		if(cnt[fi]==0) res[k]++;
		cnt[fi]++;
	}
	
	for(int j=k-1;j>=0;j--){
		isdel[del[j]]=0;
		for(int i=0;i<e[del[j]].size();i++){
			if(isdel[e[del[j]][i]]) continue;
			int fi=find(e[del[j]][i]),fj=find(del[j]);
			if(fi!=fj){
				fa[fj]=fi;
			}
		}
		memset(cnt,0x00,sizeof(cnt));
		for(int i=0;i<n;i++){
			if(isdel[i]) continue;
			int fi=find(i);
			if(cnt[fi]==0) res[j]++;
			cnt[fi]++;
		}
	}
……

改前

……
	int cnt=0;
	for(int i=0;i<n;i++){
		if(isdel[i]) continue;
		for(int j=0;j<e[i].size();j++){
			if(isdel[e[i][j]]) continue;
			int fi=find(i),fj=find(e[i][j]);
			if(fi!=fj){
				fa[fj]=fi;
				cnt++;
			}
		}
	}
	res[k]=n-k-cnt;
	
	for(int j=k-1;j>=0;j--){
		isdel[del[j]]=0;
		for(int i=0;i<e[del[j]].size();i++){
			if(isdel[e[del[j]][i]]) continue;
			int fi=find(e[del[j]][i]),fj=find(del[j]);
			if(fi!=fj){
				fa[fj]=fi;
				cnt++;
			}
		}
		res[j]=n-j-cnt;
	}
……

改后,过了,AC100

2025/2/8 16:59
加载中...