Submission #753505

#	Time	Username	Problem	Language	Result	Execution time	Memory
753505		MetalPower	Park (BOI16_park)	C++14	100 / 100	592 ms	31136 KiB

park

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define pli pair<int, pii>
#define fi first
#define se second

const int MX = 2e3 + 50;
const int MN = 1e5 + 10;

int N, M, W, H, x[MX], y[MX], r[MX];
vector<pli> edges; // weight, u, v
vector<pli> queries;

string ans[MN];

struct dsu{
	int p[MX];

	void init(){
		for(int i = 0; i < MX; i++) p[i] = i;
	}

	int f(int x){
		if(p[x] == x) return x;
		else return p[x] = f(p[x]);
	}

	void Join(int u, int v){
		int fu = f(u), fv = f(v);
		if(fu == fv) return;
		p[fu] = fv;
	}

	bool con(int u, int v){
		return f(u) == f(v);
	}
} D;

int diff(int a, int b){
	return (a > b ? a - b : b - a);
}

int bin_sqrt(ll x){
	int lf = 0, rg = 1e9, memo = -1;
	while(lf <= rg){
		int mid = lf + rg >> 1;
		if(1ll * mid * mid <= x) memo = mid, lf = mid + 1;
		else rg = mid - 1;
	}
	return memo;
}

bool check(int a, int b){ // check if entrance a and b is connected or not
	if(a == b) return true;
	if(a > b) swap(a, b);

	bool ex = !D.con(N + a, N + a % 4 + 1) && !D.con(N + b, N + b % 4 + 1);

	if((a == 1 && b == 2) || (a == 3 && b == 4)) return ex && !D.con(N + 2, N + 4);
	else if((a == 1 && b == 3) || (a == 2 && b == 4)) return ex && !D.con(N + 2, N + 4) && !D.con(N + 1, N + 3);
	else if((a == 1 && b == 4) || (a == 2 && b == 3)) return ex && !D.con(N + 1, N + 3);
	else return ex;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M >> W >> H;

	D.init();

	for(int i = 1; i <= N; i++){
		cin >> x[i] >> y[i] >> r[i];
		edges.push_back({(x[i] - r[i]) / 2, {N + 1, i}}); // maximum integer radius that can pass, aka is disconnected
		edges.push_back({(y[i] - r[i]) / 2, {N + 2, i}}); 
		edges.push_back({(W - x[i] - r[i]) / 2, {N + 3, i}});
		edges.push_back({(H - y[i] - r[i]) / 2, {N + 4, i}});
	}

	for(int i = 1; i <= N; i++){
		for(int j = i + 1; j <= N; j++){
			int dx = diff(x[i], x[j]), dy = diff(y[i], y[j]);
			int dist = (int) bin_sqrt(1ll * dx * dx + 1ll * dy * dy) - r[i] - r[j];
			edges.push_back({dist / 2, {i, j}});
		}
	}

	for(int i = 1; i <= M; i++){
		int rd, st; cin >> rd >> st;
		queries.push_back({rd, {st, i}});
	}

	int sz = edges.size();
	sort(edges.begin(), edges.end());
	sort(queries.begin(), queries.end());

	int j = 0;
	for(pli q : queries){
		for(; j < sz && edges[j].fi < q.fi; j++) D.Join(edges[j].se.fi, edges[j].se.se);

		for(int i = 1; i <= 4; i++){
			if(check(q.se.fi, i)) ans[q.se.se] += (char)(i + '0');
		}
	}

	for(int i = 1; i <= M; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

park.cpp: In function 'int bin_sqrt(long long int)':
park.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid = lf + rg >> 1;
      |             ~~~^~~~

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