Submission #349398

#	Time	Username	Problem	Language	Result	Execution time	Memory
349398		sinamhdv	Park (BOI16_park)	C++11	31 / 100	2546 ms	876 KiB

park

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 2020

int n, m;
int w, h;
int tx[MAXN], ty[MAXN], tr[MAXN];
int ans[5][5];
int cn;
int comp[MAXN];

int crad;

bool olap(int a, int b)
{
	if (a > n && b > n)
		return false;
	if (a > b)
		swap(a, b);
	if (b > n)	// C - L
	{
		b -= n;
		int d;
		if (b == 1)
			d = ty[a] - crad;
		else if (b== 2)
			d = w - tx[a] - crad;
		else if (b == 3)
			d = h - ty[a] - crad;
		else if (b == 4)
			d = tx[a] - crad;

		return (tr[a] + crad > d);
	}
	else	// C - C
	{
		int dx = abs(tx[a] - tx[b]);
		int dy = abs(ty[a] - ty[b]);
		int dr = tr[a] + tr[b] + 2 * crad;
		return ((ll)dr * dr > (ll)dx*dx + (ll)dy*dy);
	}
}

void dfs(int v)
{
	comp[v] = cn;
	FOR(i, 1, n + 5)
	{
		if (comp[i] || !olap(v, i))
			continue;
		dfs(i);
	}
}

bool check(int r, int src, int dst)
{
	memset(comp, 0, sizeof(comp));
	cn = 0;

	crad = r;

	FOR(i, 1, n + 5)
	{
		if (!comp[i])
		{
			cn++;
			dfs(i);
		}
	}

	//dbgr(comp + 1, comp + n + 5);

	dbgr(comp + n + 1, comp + n + 5);

	if (abs(src - dst) == 2)
	{
		int x1 = src + n;
		int x2 = (src % 4) + 1 + n;
		int y1 = dst + n;
		int y2 = (dst % 4) + 1 + n;

		dbg(src);
		dbg(dst);
		//cout << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;

		return (comp[x1] != comp[y2] && comp[x1] != comp[y1] && comp[x2] != comp[y1] && comp[x2] != comp[y2]);
	}
	else
	{
		if (src > dst)
			swap(src, dst);
		if (src == 1 && dst == 4)
			swap(src, dst);

		dbg(src);
		dbg(dst);

		bool res = true;
		FOR(i, 1, 5)
			if (i != src)
				res &= (comp[src + n] != comp[i + n]);
		return res;
	}
}

int32_t main(void)
{
	//fast_io;
	scanf("%d %d %d %d", &n, &m, &w, &h);
	FOR(i, 1, n + 1)
	{
		scanf("%d %d %d", tx + i, ty + i, tr + i);
	}
/*
	while (true)
	{
		int s, d, r;
		cin >> r >> s >> d;
		cout << check(r, s, d) << endl << flush;
	}
	*/

	FOR(e1, 1, 4)
	{
		FOR(e2, e1 + 1, 5)
		{
			int l = 1, r = INF + 10;
			if (!check(l, e1, e2))
			{
				ans[e1][e2] = -1;
				continue;
			}
			while (r - l > 1)
			{
				int mid = (r + l) / 2;
				if (check(mid, e1, e2))
					l = mid;
				else
					r = mid;
			}
			ans[e1][e2] = l;
		}
	}



	while (m--)
	{
		int r, e;
		scanf("%d %d", &r, &e);
		char res[8] = {0,0,0,0,0,0,0,0};
		char *ptr = res;
		FOR(i, 1, 5)
		{
			if (e == i || ans[e][i] >= r || ans[i][e] >= r)
				*ptr++ = (i + '0');
		}
		puts(res);
	}
	return 0;
}

Compilation message (stderr)

park.cpp: In function 'int32_t main()':
park.cpp:135:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |  scanf("%d %d %d %d", &n, &m, &w, &h);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |   scanf("%d %d %d", tx + i, ty + i, tr + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  176 |   scanf("%d %d", &r, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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