Submission #1129189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129189		Lecorbio	Park (BOI16_park)	C++20	27 / 100	585 ms	28292 KiB

park

#include <bits/stdc++.h>
#define fi first
#define se second
#define sajz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll x, ll y) {return uniform_int_distribution<ll>(x, y)(rng);}

const int N = 2007, Q = 1e5+7;
int n, q, w, h, par[N], sz[N]; string ans[Q];
array<int,3> circle[N], query[Q];
bool res[5][5];

bool check(int i, int j, int x){
	auto [x1, y1, r1] = circle[i];
	auto [x2, y2, r2] = circle[j];
	ll d1 = ll(x1-x2)*(x1-x2) + ll(y1-y2)*(y1-y2);
	ll d2 = ll(r1+r2+x)*(r1+r2+x);
	return d2 >= d1;
}

int Find(int x) {return (x == par[x] ? x : par[x] = Find(par[x]));}
void Union(int x, int y){
	x = Find(x); y = Find(y);
	if (x != y){
		if (sz[x] < sz[y]) swap(x, y);
		par[y] = x;
		sz[x] += sz[y];
	}
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> q >> w >> h;
    for (int i=1; i<=n; i++){
		int x, y, r; cin >> x >> y >> r;
		circle[i] = {x, y, r};
	}
	for (int i=0; i<q; i++){
		int r, c; cin >> r >> c;
		c += 'A' - 1;
		query[i] = {r, c, i};
	}
	sort(query, query+q);
	
	//n+1 - gora, n+2 - dol, n+3 - lewo, n+4 - prawo
	vector<array<int,3>> edge;
	for (int i=1; i<=n; i++) for (int j=i+1; j<=n+4; j++){
		if (j <= n){
			int l = 0, r = 1e9;
			while (l < r){
				int mid = (l+r)/2;
				if (check(i, j, mid)) r = mid;
				else l = mid+1;
			}
			edge.push_back({l, i, j});
		}else if (j == n+1) edge.push_back({h - circle[i][1] - circle[i][2], i, j});
		else if (j == n+2) edge.push_back({circle[i][1] - circle[i][2], i, j});
		else if (j == n+3) edge.push_back({circle[i][0] - circle[i][2], i, j});
		else if (j == n+4) edge.push_back({w - circle[i][0] - circle[i][2], i, j});
	}
	sort(all(edge));
	//for (auto [d, a, b] : edge) cout << a << ' ' << b << ": " << d << '\n';
	
	for (int i=1; i<=n+4; i++) {par[i] = i; sz[i] = 1;}
	for (int i=1; i<=4; i++) for (int j=1; j<=4; j++) res[i][j] = true;
	
	vector<char> ele = {'?', 'A', 'B', 'C', 'D'};
	int j = -1;
	for (int i=0; i<q; i++){
		auto [r, c, ind] = query[i];
		//cout << i << ' ' << r << " -----------\n";
		while (j+1 < sajz(edge) && edge[j+1][0] < 2*r){
			j++;
			auto [d, a, b] = edge[j];
			Union(a, b);
			//cout << d << ' ' << a << ' ' << b << '\n';
		}
		//for (int k=1; k<=n+4; k++) cout << k << ": " << Find(k) << '\n';
		
		if (Find(n+2) == Find(n+3)){
			for (int k=1; k<=4; k++) if (k != 1) res[1][k] = res[k][1] = false;
		}
		if (Find(n+2) == Find(n+4)){
			for (int k=1; k<=4; k++) if (k != 2) res[2][k] = res[k][2] = false;
		}
		if (Find(n+1) == Find(n+4)){
			for (int k=1; k<=4; k++) if (k != 3) res[3][k] = res[k][3] = false;
		}
		if (Find(n+1) == Find(n+3)){
			for (int k=1; k<=4; k++) if (k != 4) res[4][k] = res[k][4] = false;
		}
		if (Find(n+1) == Find(n+2)){
			res[1][2] = res[1][3] = res[4][2] = res[4][3] = false;
			res[2][1] = res[2][1] = res[3][4] = res[3][4] = false;
		}
		if (Find(n+3) == Find(n+4)){
			res[1][3] = res[1][4] = res[2][3] = res[2][4] = false;
			res[3][1] = res[3][2] = res[4][1] = res[4][2] = false;
		}
		//for (int k=1; k<=4; k++){
			//cout << k << ": ";
			//for (int k2=1; k2<=4; k2++) if (res[k][k2]) cout << ele[k2] << ' '; cout << '\n';
		//}
		for (int k=1; k<=4; k++) if (res[c-'A'+1][k]) ans[ind] += ele[k];
	}
	//for (int i=0; i<q; i++) cout << ans[i] << '\n';
	for (int i=0; i<q; i++){
		string s = ans[i];
		for (auto c : s) cout << c - 'A' + 1;
		cout << '\n';
	}
    return 0;
}
/*

5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

5 3 16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 A
2 B
2 A

*/

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