站外题目求调,悬关
  • 板块学术版
  • 楼主wxw_zl
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/2/26 17:41
  • 上次更新2024/2/26 20:27:02
查看原帖
站外题目求调,悬关
469487
wxw_zl楼主2024/2/26 17:41

问题:Segmentation fault

数据范围: 2<=n<=5002<=n<=500,1<=ki<=1091<=k_i<=10^9 1<=bi<=105,1<+T<=101<=b_i<=10^5,1<+T<=10

代码

#include<bits/stdc++.h>
#define rise(i,l,r) for(int (i)=(l);(i)<=(r);(i)++)
#define fall(i,r,l) for(int (i)=(r);(i)>=(l);(i)--)
using namespace std;
const int maxn=5500;
int t,n,m;
int vis[maxn];
int a[maxn],k[maxn];
double dis[maxn][maxn];
void init() {
	rise(i,1,n) {
		rise(j,1,n) {
			dis[i][j]=-1;
		}
	}
	memset(vis,-1,sizeof vis);
	rise(i,1,n) {
		rise(j,1,n) {
			if(i==j)continue;
			if(k[i]==k[j]) {
				if(a[i]==a[j])dis[i][j]=dis[j][i]=0;
			} else if((k[i]-k[j])*(a[i]-a[j])<0) {
				dis[i][j]=dis[j][i]=1.0*(a[j]-a[i])/(k[i]-k[j]);//计算相交的时间
			}
		}
	}
}
void in() {
	cin>>n>>m;
	rise(i,1,n)cin>>a[i];
	rise(i,1,m)cin>>k[i];
}
void bfs(int st) {
	queue<int>q;
	q.push(st);
	vis[st]=0;
	while(q.size()) {
		int u=q.front();
		q.pop();
		rise(i,1,n) {
			if(vis[i]!=-1||dis[u][i]==-1)continue;

			if(dis[u][i]>=vis[u]) {
				vis[i]=dis[u][i];
				q.push(i);
			}
		}
	}
}
int cntans() {
	int res=0;
	rise(i,1,n) {
		if(vis[i]!=-1)res++;
	}
	return res;
}
int main() {
	freopen("animal.in","r",stdin);
	freopen("animal.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>t;
	rise(i,1,t) {
		in();
		init();
		bfs(m);
		cout<<cntans()<<"\n";
	}
	return 0;
}
2024/2/26 17:41
加载中...