社区讨论

进士厚仁,如果你40分TLE

P1197[JSOI2008] 星球大战参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m6vysd2e
此快照首次捕获于
2025/02/08 16:59
去年
此快照最后确认于
2025/11/04 09:43
4 个月前
查看原帖
统计请用减法,合一个减一,不要单独统计,会被卡
CPP
……
	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]++;
		}
	}
……
改前
CPP
……
	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

回复

1 条回复,欢迎继续交流。

正在加载回复...