用数字就Ac了?
  • 板块灌水区
  • 楼主fang20081114
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/18 23:22
  • 上次更新2024/8/18 23:43:10
查看原帖
用数字就Ac了?
470299
fang20081114楼主2024/8/18 23:22

求dalao解释:下方两代码仅主函数中第一个for循环的限制不同,而 N 的初始值就等30000,为什么第一个代码测评机上不能跑但本地可以跑;第二个代码可以Ac P1196 银河英雄传说

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int m;
int f[N],s[N],d[N];//d[i]表示i到p[i]的距离
int find(int x){
	if(f[x]!=x){
		int root=find(f[x]);
		d[x]+=d[f[x]];//路径压缩
		f[x]=root;
	}
	return f[x];
}
int main(){
	scanf("%d",&m);
	for(int i=1;i<=N;i++){
		s[i]=1;
		f[i]=i;
	}
	while(m--){
		char op[2];
		int a,b;
		scanf("%s%d%d",op,&a,&b);
		int pa=find(a),pb=find(b);
		if(op[0]=='M'&&pa!=pb){
			d[pa]=s[pb];
			s[pb]+=s[pa];
			f[pa]=pb;
		}else if(op[0]=='C'){
			if(pa!=pb) puts("-1");
			else printf("%d\n",max(0,abs(d[a]-d[b])-1));
		}
	}
	return 0;
}

二、

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int m;
int f[N],s[N],d[N];//d[i]表示i到p[i]的距离
int find(int x){
	if(f[x]!=x){
		int root=find(f[x]);
		d[x]+=d[f[x]];//路径压缩
		f[x]=root;
	}
	return f[x];
}
int main(){
	scanf("%d",&m);
	for(int i=1;i<=30000;i++){
		s[i]=1;
		f[i]=i;
	}
	while(m--){
		char op[2];
		int a,b;
		scanf("%s%d%d",op,&a,&b);
		int pa=find(a),pb=find(b);
		if(op[0]=='M'&&pa!=pb){
			d[pa]=s[pb];
			s[pb]+=s[pa];
			f[pa]=pb;
		}else if(op[0]=='C'){
			if(pa!=pb) puts("-1");
			else printf("%d\n",max(0,abs(d[a]-d[b])-1));
		}
	}
	return 0;
}
2024/8/18 23:22
加载中...