Submission #578433

#	Time	Username	Problem	Language	Result	Execution time	Memory
578433		Shreyan_Paliwal	Park (BOI16_park)	C++17	100 / 100	857 ms	65040 KiB

park

#include <bits/stdc++.h>

using namespace std;

const long long MAXN = 2005;
const long long INF  = 2000000000;

long long n, m;
long long w, h;
pair<long long,long long> coords[MAXN]; 
long long radii[MAXN];
double distances[MAXN][MAXN];
vector<pair<long long,long long>> dist_sorted;
double wallsconnected[4][4];

long long root[MAXN], depth[MAXN];

long long find(long long k) {
	if (k == root[k]) return k;
	return root[k] = find(root[k]);
}

bool same(long long a, long long b) {return find(a) == find(b); }

void unite(long long a, long long b) {
	a = find(a), b = find(b);
	if (a == b) return;
	if (depth[a] < depth[b]) root[a]=b;
	else root[b]=a, depth[a] += (depth[a]==depth[b]);
}

long long sq(long long x) {return x*x;}

double dist(long long a, long long b) {
	return sqrt(sq(coords[a].first - coords[b].first) + sq(coords[a].second - coords[b].second))
	             - radii[a] - radii[b]; 
}

int main() {
	cin >> n >> m;
	cin >> w >> h;
	for (long long i = 0; i < n; i++) cin >> coords[i].first >> coords[i].second >> radii[i];

	for (long long i = 0; i < n; i++) 
	  for (long long j = i + 1; j < n; j++) 
		  distances[j][i] = distances[i][j] = dist(i, j);

	for (long long i = 0; i < n; i++) 
	  distances[n+3][i] = distances[i][n+3] = h - coords[i].second - radii[i];
	
	for (long long i = 0; i < n; i++) 
	  distances[n+2][i] = distances[i][n+2] = w - coords[i].first - radii[i];
	
	for (long long i = 0; i < n; i++) 
	  distances[n+1][i] = distances[i][n+1] = coords[i].second - radii[i];
	
	for (long long i = 0; i < n; i++) 
	  distances[n][i] = distances[i][n] = coords[i].first - radii[i];
		
	for (long long i = 0; i < n; i++) 
		for (long long j = i+1; j < n+4; j++) 
		  dist_sorted.push_back({i, j});

	sort(dist_sorted.begin(), dist_sorted.end(), [](pair<long long,long long> a, pair<long long,long long> b) {
		return distances[a.first][a.second] < distances[b.first][b.second];
	});
	
	for (long long i = 0; i < 4; i++) for (long long j = 0; j < 4; j++) wallsconnected[i][j] = INF;

	for (long long i = 0; i < MAXN; i++) root[i]=i;
	for (long long i = 0; i < MAXN; i++) depth[i]=1;

	for (auto i : dist_sorted) {
		unite(i.first, i.second);
		//cout << i.first << " " << i.second << " " << distances[i.first][i.second] << '\n';
		for (long long j = 0; j < 4; j++) { 
			for (long long k = 0; k < 4; k++) {
				if (j == k) continue;
				if (wallsconnected[j][k] == INF && same(n + j, n + k)) {
					wallsconnected[j][k] = distances[i.first][i.second];
					//cout << j << " " << k << '\n';
				}
			}
		}
	}

	for(long long i = 0; i < 4; i++)
		for(long long j = 0; j < 4; j++){
			//cout << wallsconnected[i][j] << (j < 3 ? ' ' : '\n');
		}

	for (long long i = 0; i < m; i++) {
		double r; long long e; cin >> r >> e;
		e--;
		for(long long j = 0; j < 4; j++) {
			bool works = 1;
			if(j != e){
				works &= wallsconnected[e][(e + 1) % 4] >= 2*r;
				//cout << wallsconnected[e][(e+1)%4] << " ";
				works &= wallsconnected[j][(j + 1) % 4] >= 2*r;
				//cout << wallsconnected[j][(j+1)%4] << " ";
				if((4 + j - e) % 4 >= 2){
					works &= wallsconnected[e][(e + 2) % 4] >= 2*r;
				}
				if((4 + j - e) % 4 <= 2){
					works &= wallsconnected[(e + 1) % 4][(e + 3) % 4] >= 2*r;
				}
			}
			if(works) cout << char('1' + j);
			//cout << endl;
		}
		cout << '\n';
	}





}

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