oj.uz

Submission #578433

# Submission time Handle Problem Language Result Execution time Memory
578433 2022-06-16T21:36:53 Z Shreyan_Paliwal Park (BOI16_park) C++17
100 / 100
 857 ms 65040 KB 
#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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 64800 KB Output is correct
2 Correct 589 ms 64784 KB Output is correct
3 Correct 613 ms 64812 KB Output is correct
4 Correct 617 ms 64732 KB Output is correct
5 Correct 608 ms 64816 KB Output is correct
6 Correct 597 ms 64788 KB Output is correct
7 Correct 446 ms 64816 KB Output is correct
8 Correct 496 ms 64768 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 3336 KB Output is correct
2 Correct 234 ms 3284 KB Output is correct
3 Correct 225 ms 3172 KB Output is correct
4 Correct 206 ms 3272 KB Output is correct
5 Correct 220 ms 3352 KB Output is correct
6 Correct 228 ms 3576 KB Output is correct
7 Correct 215 ms 1936 KB Output is correct
8 Correct 210 ms 1952 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 64800 KB Output is correct
2 Correct 589 ms 64784 KB Output is correct
3 Correct 613 ms 64812 KB Output is correct
4 Correct 617 ms 64732 KB Output is correct
5 Correct 608 ms 64816 KB Output is correct
6 Correct 597 ms 64788 KB Output is correct
7 Correct 446 ms 64816 KB Output is correct
8 Correct 496 ms 64768 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 218 ms 3336 KB Output is correct
12 Correct 234 ms 3284 KB Output is correct
13 Correct 225 ms 3172 KB Output is correct
14 Correct 206 ms 3272 KB Output is correct
15 Correct 220 ms 3352 KB Output is correct
16 Correct 228 ms 3576 KB Output is correct
17 Correct 215 ms 1936 KB Output is correct
18 Correct 210 ms 1952 KB Output is correct
19 Correct 798 ms 65040 KB Output is correct
20 Correct 806 ms 65020 KB Output is correct
21 Correct 817 ms 64928 KB Output is correct
22 Correct 805 ms 64916 KB Output is correct
23 Correct 857 ms 64940 KB Output is correct
24 Correct 695 ms 64928 KB Output is correct