社区讨论

实在是不理解 ,样例和第一个测试点都过了,输出一模一样 , 为什么还是爆0

P3958[NOIP 2017 提高组] 奶酪参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lo2vo8e1
此快照首次捕获于
2023/10/23 20:32
2 年前
此快照最后确认于
2023/10/23 20:32
2 年前
查看原帖
CPP
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e3 + 10;
int T , n , h , r ,f[N];;
struct pll{
	int x, y, z;
	bool operator<(const pll &w) const
	{
		return z < w.z;
	}
}p[N];
void init() {
	for(int i = 1 ; i <= n ; ++i) f[i] = i;
}
int find(int x){
	if(x == f[x]) return x ;
	else return f[x] = find(f[x]);
}
int sqr(int x){
	return x * x;
}
int main()
{
	cin >> T;
	while(T--)
	{
		cin >> n >> h >> r;
		init();
		int tf = 0;
		for(int i = 1 ; i <= n ; ++i) 
		{
			cin >> p[i].x >> p[i].y >> p[i].z;
			if(p[i].z + r >= h && p[i].z - r <= 0){
				puts("Yes");
				tf = 1;
				break;
			}
		}
		
		if(tf) continue;
		
		for (int i = 1 ; i <= n ; ++i)
		{
			for(int j = i + 1 ; j <= n ; ++j){
				int fa = find(i) , fb = find(j);				
				if(fa != fb){
					int w = sqr(p[i].x - p[j].x) + sqr(p[i].y - p[j].y) + sqr(p[i].z - p[j].z);
					if(w <= sqr(r + r))	
					{
						f[fa] = fb;	
					}
				}
			}
		}
		
		sort(p + 1 , p + n + 1);
		int gw = 1;
		
		for (int i = 1 ; i <= n ; ++i)
		{
			if(p[i].z - r > 0) break;
			for(int j = n ; j > i ; --j)
			{
				if(p[j].z + r < h) break;
				int fa = find(i) , fb = find(j);
				if(fa == fb){
					puts("Yes");
					gw = 0;
				}
			}
		}
		
		if(gw) puts("No");
		
	}
}

回复

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

正在加载回复...