oj.uz

Submission #349391

# Submission time Handle Problem Language Result Execution time Memory
349391 2021-01-17T14:03:55 Z sinamhdv Park (BOI16_park) C++11
31 / 100
 2500 ms 784 KB 
#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;
		ll d;
		if (b == 1)
			d = (ll)ty[a] - crad;
		else if (b== 2)
			d = (ll)w - tx[a] - crad;
		else if (b == 3)
			d = (ll)h - ty[a] - crad;
		else if (b == 4)
			d = (ll)tx[a] - crad;

		return ((ll)tr[a] + crad > d);
	}
	else	// C - C
	{
		ll dx = llabs(tx[a] - tx[b]);
		ll dy = llabs(ty[a] - ty[b]);
		ll dr = (ll)tr[a] + tr[b] + (ll)2 * crad;
		return (dr * dr > dx*dx + 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 (llabs(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;
	cin >> n >> m;
	cin >> w >> h;
	FOR(i, 1, n + 1)
	{
		cin >> 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;
		cin >> r >> e;
		string res;
		FOR(i, 1, 5)
		{
			if (e == i || ans[e][i] >= r || ans[i][e] >= r)
				res += (i + '0');
		}
		cout << res << endl;
	}
	return 0;
}

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2551 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 784 KB Output is correct
2 Correct 61 ms 748 KB Output is correct
3 Correct 63 ms 748 KB Output is correct
4 Correct 63 ms 748 KB Output is correct
5 Correct 66 ms 748 KB Output is correct
6 Correct 45 ms 748 KB Output is correct
7 Correct 28 ms 620 KB Output is correct
8 Correct 28 ms 620 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2551 ms 364 KB Time limit exceeded
2 Halted 0 ms 0 KB -