Submission #748455

#	Time	Username	Problem	Language	Result	Execution time	Memory
748455		mariowong	Park (BOI16_park)	C++14	100 / 100	301 ms	38800 KiB

park

#include <bits/stdc++.h>
 
using namespace std;
 
int n,m,pt,id,indx;
long long w,h,x[2005],y[2005],r[2005],dsu[2005];
pair<pair <long long,int>,int> visitor[100005];
string ans[100005];
vector <pair<long long,pair<int,int>  >  > update;
long long sqr(long long v){
	return v*v;
}
long long distance(int a1,int a2){
	return (long long)(sqrt(sqr(x[a1]-x[a2])+sqr(y[a1]-y[a2])))+1;
}
long long find(int x){
	if (dsu[x] == x)
	return x;
	return dsu[x]=find(dsu[x]);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> w >> h;
	for (int i=1;i<=n;i++){
		cin >> x[i] >> y[i] >> r[i];
		dsu[i]=i;
	}
	dsu[n+1]=n+1; dsu[n+2]=n+2; dsu[n+3]=n+3; dsu[n+4]=n+4;
	for (int i=1;i<=n;i++){
		update.push_back(make_pair(x[i]-r[i]+1,make_pair(i,n+1)));
		update.push_back(make_pair(h-(y[i]+r[i])+1,make_pair(i,n+2)));
		update.push_back(make_pair(w-(x[i]+r[i])+1,make_pair(i,n+3)));
		update.push_back(make_pair(y[i]-r[i]+1,make_pair(i,n+4)));
		for (int j=i+1;j<=n;j++){
			update.push_back(make_pair(distance(i,j)-r[i]-r[j],make_pair(i,j)));
		}
	}
	for (int i=1;i<=m;i++){
		cin >> visitor[i].first.first >> visitor[i].first.second;
		visitor[i].second=i;
	}
	sort(visitor+1,visitor+m+1); sort(update.begin(),update.end());
	for (int i=1;i<=m;i++){
		while (pt < (int)update.size() && update[pt].first <= visitor[i].first.first*2){
			if (find(update[pt].second.first) != find(update[pt].second.second))
			dsu[find(update[pt].second.first)]=find(update[pt].second.second);
			pt++;
		}
		id=visitor[i].first.second; indx=visitor[i].second;
		ans[indx]+=char(id+'0');
		if (id == 1){
			if (find(n+4) != find(n+3) && find(n+4) != find(n+2) && find(n+1) != find(n+4)) ans[indx]+='2';//2
			if (find(n+2) != find(n+3) && find(n+4) != find(n+2) && find(n+1) != find(n+3) && find(n+1) != find(n+4)) ans[indx]+='3';//3
			if (find(n+1) != find(n+2) && find(n+1) != find(n+3) && find(n+1) != find(n+4)) ans[indx]+='4';//4
		}
		else
		if (id == 2){
			if (find(n+1) != find(n+4) && find(n+4) != find(n+2) && find(n+4) != find(n+3)) ans[indx]+='1';//1
			if (find(n+2) != find(n+3) && find(n+1) != find(n+3) && find(n+4) != find(n+3)) ans[indx]+='3';//3
			if (find(n+1) != find(n+2) && find(n+1) != find(n+3) && find(n+2) != find(n+4) && find(n+4) != find(n+3)) ans[indx]+='4';//4
		}
		else
		if (id == 3){
			if (find(n+1) != find(n+4) && find(n+4) != find(n+2) && find(n+1) != find(n+3) && find(n+2) != find(n+3)) ans[indx]+='1';//1
			if (find(n+3) != find(n+4) && find(n+1) != find(n+3) && find(n+2) != find(n+3)) ans[indx]+='2';//2
			if (find(n+1) != find(n+2) && find(n+2) != find(n+4) && find(n+2) != find(n+3)) ans[indx]+='4';//4	
		}
		else
		if (id == 4){
			if (find(n+4) != find(n+1) && find(n+1) != find(n+3) && find(n+1) != find(n+2)) ans[indx]+='1';//1
			if (find(n+4) != find(n+3) && find(n+4) != find(n+2) && find(n+1) != find(n+3) && find(n+1) != find(n+2)) ans[indx]+='2';//2
			if (find(n+3) != find(n+2) && find(n+2) != find(n+4) && find(n+1) != find(n+2)) ans[indx]+='3';//3
		}
	}
	for (int i=1;i<=m;i++){
		sort(ans[i].begin(),ans[i].end());
		cout << ans[i] << "\n";
	}
	return 0;
}

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