oj.uz

Submission #932691

# Submission time Handle Problem Language Result Execution time Memory
932691 2024-02-24T03:16:21 Z abcdehello Park (BOI16_park) C++17
27 / 100
 241 ms 53952 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<=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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 52404 KB Output is correct
2 Correct 235 ms 52924 KB Output is correct
3 Correct 231 ms 52696 KB Output is correct
4 Correct 235 ms 53952 KB Output is correct
5 Correct 237 ms 53692 KB Output is correct
6 Correct 235 ms 53168 KB Output is correct
7 Correct 217 ms 53436 KB Output is correct
8 Correct 211 ms 53164 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 Incorrect 60 ms 9316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 52404 KB Output is correct
2 Correct 235 ms 52924 KB Output is correct
3 Correct 231 ms 52696 KB Output is correct
4 Correct 235 ms 53952 KB Output is correct
5 Correct 237 ms 53692 KB Output is correct
6 Correct 235 ms 53168 KB Output is correct
7 Correct 217 ms 53436 KB Output is correct
8 Correct 211 ms 53164 KB Output is correct
9 Correct 1 ms 2648 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Incorrect 60 ms 9316 KB Output isn't correct
12 Halted 0 ms 0 KB -