Submission #932711

#	Time	Username	Problem	Language	Result	Execution time	Memory
932711		abcdehello	Park (BOI16_park)	C++17	100 / 100	321 ms	58140 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 separation(tree a,tree b){
	return dist(a,b)-1.00*a.r-1.00*b.r;
}
ll n,m,w,h,p[2050],con[5][5];
tree t[2050];
vector<pair<pll,ll>> qry;
vector<pdll> sep;
vector<int> ans[100050];
int find(int u){
	if (p[u]!=u) p[u]=find(p[u]);
	return p[u];
}
bool isConnected(int u,int v){
	return find(u)==find(v);
}
void uni(int u,int v){
	p[find(u)]=find(v);
}
int main(){
	cin >> n >> m;
	cin >> w >> h;
	for (int i=1;i<=n+10;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++){
		ll e,r;
		cin >> r >> e;
		qry.push_back({{r*2,e},i});
	}
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			sep.push_back({separation(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 border
		sep.push_back({t[i].y-t[i].r,{i,n+2}});//down border
		sep.push_back({w-t[i].x-t[i].r,{i,n+3}});//right border
		sep.push_back({h-t[i].y-t[i].r,{i,n+4}});//up border
	}
	sort(sep.begin(),sep.end());
	reverse(sep.begin(),sep.end());
	sort(qry.begin(),qry.end());
	for (auto q:qry){
		ll d=q.f.f,e=q.f.s,ind=q.s;
		while (sep.size()&&sep.back().f<d) uni(sep.back().s.f,sep.back().s.s),sep.pop_back();
		for (int i=1;i<=4;i++) for (int j=1;j<=4;j++) con[i][j]=1;
		for (int i=1;i<=4;i++){
			if (isConnected(n+i,n+(i%4)+1)){
				for (int j=1;j<=4;j++){
					if (i!=j) con[i][j]=con[j][i]=0;
				}
			}
		}
		if (isConnected(n+1,n+3)){
			for (int i=1;i<=2;i++){
				for (int j=3;j<=4;j++) con[i][j]=con[j][i]=0;
			}
		}
		if (isConnected(n+2,n+4)){
			con[1][2]=con[1][3]=con[2][1]=con[3][1]=0;
			con[4][2]=con[4][3]=con[2][4]=con[3][4]=0;
		}
		for (int i=1;i<=4;i++) if (con[e][i]) ans[ind].push_back(i);
	}
	for (int i=1;i<=m;i++) sort(ans[i].begin(),ans[i].end());
	for (int i=1;i<=m;i++){
		for (int j:ans[i]) cout << j;
		cout << "\n";
	}
}

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