Submission #932687

#	Time	Username	Problem	Language	Result	Execution time	Memory
932687		abcdehello	Park (BOI16_park)	C++17	0 / 100	2545 ms	57632 KiB

park

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<double,pll> pdll;
#define f first
#define s second
struct tree{
	ll x,y,r;
};
double dist(tree a,tree b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double spaceBetween(tree a,tree b){
	return max(0.0,dist(a,b)-a.r-b.r);
}
ll n,m,w,h,p[2050];
tree t[2050];
vector<int> ans[100050];
vector<pdll> sep;
vector<pair<pll,ll>> qry;
int find(int u){
	if (u!=p[u]) p[u]=find(p[u]);
	return p[u];
}
bool isConnected(int u,int v){
	return find(u)==find(v);
}
int main(){
	cin >> n >> m;
	cin >> w >> h;
	for (int i=1;i<=n+4;i++) p[i]=i;
	for (int i=1;i<=n;i++){
		cin >> t[i].x >> t[i].y >> t[i].r;
	}
	for (int i=1;i<=m;i++){
		int e,r;
		cin >> r >> e;
		qry.push_back({{r,e},i});
	}
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++) sep.push_back({spaceBetween(t[i],t[j]),{i,j}});
	}
	for (int i=1;i<=n;i++){
		sep.push_back({t[i].x-t[i].r,{i,n+1}});//left
		sep.push_back({t[i].y-t[i].r,{i,n+2}});//down
		sep.push_back({w-t[i].x-t[i].r,{i,n+3}});//right
		sep.push_back({h-t[i].y-t[i].r,{i,n+4}});//up
	}
	sort(sep.begin(),sep.end());
	sort(qry.begin(),qry.end());
	int nxt=0;
	for (auto q:qry){
		while (sep[nxt].f<2*q.f.f) cerr << "*" << sep[nxt].f << endl,p[find(sep[nxt].s.f)]=find(sep[nxt].s.s),nxt++;
		int ind=q.s,e=q.f.s;
		ans[ind].push_back(e);
		//cerr << ind << " " << e << " " << q.f.f << endl;
		if (e==1){
			//cerr << 1 << endl;
			if (!isConnected(n+1,n+2)&&!isConnected(n+2,n+3)&&!isConnected(n+2,n+4)) ans[ind].push_back(2);
			if (!isConnected(n+1,n+2)&&!isConnected(n+3,n+4)&&!isConnected(n+1,n+3)&&!isConnected(n+2,n+4)) ans[ind].push_back(3);
			if (!isConnected(n+1,n+2)&&!isConnected(n+1,n+4)&&!isConnected(n+1,n+3)) ans[ind].push_back(4);
		}
		else if (e==2){
			//cerr << 2 << endl;
			if (!isConnected(n+2,n+3)&&!isConnected(n+3,n+4)&&!isConnected(n+3,n+1)) ans[ind].push_back(3);
			if (!isConnected(n+2,n+3)&&!isConnected(n+4,n+1)&&!isConnected(n+2,n+4)&&!isConnected(n+3,n+1)) ans[ind].push_back(4);
			if (!isConnected(n+2,n+3)&&!isConnected(n+2,n+1)&&!isConnected(n+2,n+4)) ans[ind].push_back(1);	
		}
		else if (e==3){
			//cerr << 3 << endl;
			if (!isConnected(n+3,n+4)&&!isConnected(n+4,n+1)&&!isConnected(n+4,n+2)) ans[ind].push_back(4);
			if (!isConnected(n+3,n+4)&&!isConnected(n+1,n+2)&&!isConnected(n+3,n+1)&&!isConnected(n+2,n+4)) ans[ind].push_back(1);
			if (!isConnected(n+3,n+4)&&!isConnected(n+3,n+2)&&!isConnected(n+3,n+1)) ans[ind].push_back(2);
		}
		else{
			//cerr << 4 << endl;
			if (!isConnected(n+4,n+1)&&!isConnected(n+1,n+2)&&!isConnected(n+1,n+3)) ans[ind].push_back(1);
			if (!isConnected(n+4,n+1)&&!isConnected(n+2,n+3)&&!isConnected(n+4,n+2)&&!isConnected(n+2,n+4)) ans[ind].push_back(2);
			if (!isConnected(n+4,n+1)&&!isConnected(n+4,n+3)&&!isConnected(n+4,n+2)) ans[ind].push_back(3);
		}
	}
	for (int i=1;i<=n;i++) sort(ans[i].begin(),ans[i].end());
	for (int i=1;i<=n;i++){
		for (int j:ans[i]) cout << j;
		cout << "\n";
	}
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42