oj.uz

Submission #932708

# Submission time Handle Problem Language Result Execution time Memory
932708 2024-02-24T04:16:43 Z abcdehello Park (BOI16_park) C++17
27 / 100
 244 ms 54224 KB 
#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) 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<=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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 52672 KB Output is correct
2 Correct 244 ms 52920 KB Output is correct
3 Correct 234 ms 53440 KB Output is correct
4 Correct 236 ms 53184 KB Output is correct
5 Correct 241 ms 53948 KB Output is correct
6 Correct 239 ms 54224 KB Output is correct
7 Correct 223 ms 54124 KB Output is correct
8 Correct 214 ms 53368 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 9056 KB Output is correct
2 Correct 71 ms 8888 KB Output is correct
3 Incorrect 71 ms 8892 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 52672 KB Output is correct
2 Correct 244 ms 52920 KB Output is correct
3 Correct 234 ms 53440 KB Output is correct
4 Correct 236 ms 53184 KB Output is correct
5 Correct 241 ms 53948 KB Output is correct
6 Correct 239 ms 54224 KB Output is correct
7 Correct 223 ms 54124 KB Output is correct
8 Correct 214 ms 53368 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 74 ms 9056 KB Output is correct
12 Correct 71 ms 8888 KB Output is correct
13 Incorrect 71 ms 8892 KB Output isn't correct
14 Halted 0 ms 0 KB -