Submission #78756

#	Time	Username	Problem	Language	Result	Execution time	Memory
78756		scanhex	Park (BOI16_park)	C++17	100 / 100	912 ms	79596 KiB

park

#include <bits/stdc++.h>

using namespace std;
using nagai = long long;
using ll = long long;

struct circ
{
	 int x, y, r;
};

const int N = 2004;
nagai mx[N][N];

nagai sqr(nagai x)
{
	 return x * x;
}

int p[N];
void init()
{
	iota(p, p + N, 0);
}
bool trash = (init(), 0);
int getp(int x)
{
	 return p[x] == x ? x : p[x] = getp(p[x]);
}

void unite(int a, int b)
{
	p[getp(a)] = getp(b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	int w, h;
	cin >> w >> h;
	vector<circ> mem(n);
	for (int i = 0; i < n; ++i)
		cin >> mem[i].x >> mem[i].y >> mem[i].r;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < i; ++j)
		{
			nagai L = 0, R = 2e9;
			while (R - L > 1)
			{
				 nagai M = (L + R) / 2;
				 // r[i] + r[j] + M <= hypot
				 if (sqr(mem[i].r + mem[j].r + M) <= sqr(mem[i].x - mem[j].x) + sqr(mem[i].y - mem[j].y))
					 L = M;
				 else
					 R = M;
			}
			mx[i][j] = mx[j][i] = L;
		}
	for (int i = 0; i < n; ++i)
	{
		nagai d = mem[i].y - mem[i].r;
		mx[i][n] = mx[n][i] = d;
		d = w - mem[i].x - mem[i].r;
		mx[i][n + 1] = mx[n + 1][i] = d;
		d = h - mem[i].y - mem[i].r;
		mx[i][n + 2] = mx[n + 2][i] = d;
		d = mem[i].x - mem[i].r;
		mx[i][n + 3] = mx[n + 3][i] = d;
	}
	vector<tuple<nagai, int, int>> edg;
	for (int i = 0; i < n + 4; ++i)
		for (int j = 0; j < min(i, n); ++j)
		{
			edg.emplace_back(mx[i][j], i, j);
		}
	sort(edg.begin(), edg.end());
	nagai oo = 1e18;
	vector<vector<nagai>> arr(4, vector<nagai>(4, oo));
	for (auto& x : edg)
	{
		unite(get<1>(x), get<2>(x));
		nagai mem = get<0>(x);
		for (int i = 0; i < 4; ++i)
			for (int j = 0; j < 4; ++j)
				if (getp(n + i) == getp(n + j) && arr[i][j] == oo)
					arr[i][j] = mem;
	}
	vector<vector<nagai>> go(4, vector<nagai>(4, oo));
	for (int i = 0; i < 4; ++i)
	{
		int j = (i + 1) % 4, k = (i + 2) % 4, l = (i + 3) % 4;
		go[i][j] = min(arr[i][j], min(arr[i][k], arr[i][l]));
		go[i][k] = min(min(arr[i][k], arr[j][l]), min(arr[i][l], arr[j][k]));
	}
	for (int i = 0; i < 4; ++i)
		go[i][(i + 3) % 4] = go[(i + 3) % 4][i];
	for (int i = 0; i < m; ++i)
	{
		 int r, e;
		 cin >> r >> e;
		 r *= 2;
		 --e;
		 for (int j = 0; j < 4; ++j)
			 if (go[e][j] >= r)
				 cout << j + 1;
		 cout << '\n';
	}
	return 0;
}

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