oj.uz

Submission #748455

# Submission time Handle Problem Language Result Execution time Memory
748455 2023-05-26T10:07:03 Z mariowong Park (BOI16_park) C++14
100 / 100
 301 ms 38800 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 36516 KB Output is correct
2 Correct 232 ms 36472 KB Output is correct
3 Correct 238 ms 36456 KB Output is correct
4 Correct 241 ms 36448 KB Output is correct
5 Correct 236 ms 36520 KB Output is correct
6 Correct 232 ms 36652 KB Output is correct
7 Correct 224 ms 36532 KB Output is correct
8 Correct 215 ms 36512 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 3 ms 3468 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 7624 KB Output is correct
2 Correct 45 ms 7608 KB Output is correct
3 Correct 44 ms 7616 KB Output is correct
4 Correct 44 ms 7588 KB Output is correct
5 Correct 49 ms 7628 KB Output is correct
6 Correct 48 ms 7732 KB Output is correct
7 Correct 47 ms 7252 KB Output is correct
8 Correct 45 ms 7296 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 36516 KB Output is correct
2 Correct 232 ms 36472 KB Output is correct
3 Correct 238 ms 36456 KB Output is correct
4 Correct 241 ms 36448 KB Output is correct
5 Correct 236 ms 36520 KB Output is correct
6 Correct 232 ms 36652 KB Output is correct
7 Correct 224 ms 36532 KB Output is correct
8 Correct 215 ms 36512 KB Output is correct
9 Correct 3 ms 3540 KB Output is correct
10 Correct 3 ms 3468 KB Output is correct
11 Correct 50 ms 7624 KB Output is correct
12 Correct 45 ms 7608 KB Output is correct
13 Correct 44 ms 7616 KB Output is correct
14 Correct 44 ms 7588 KB Output is correct
15 Correct 49 ms 7628 KB Output is correct
16 Correct 48 ms 7732 KB Output is correct
17 Correct 47 ms 7252 KB Output is correct
18 Correct 45 ms 7296 KB Output is correct
19 Correct 273 ms 38700 KB Output is correct
20 Correct 278 ms 38772 KB Output is correct
21 Correct 277 ms 38740 KB Output is correct
22 Correct 274 ms 38800 KB Output is correct
23 Correct 301 ms 38760 KB Output is correct
24 Correct 262 ms 38748 KB Output is correct