oj.uz

Submission #250980

# Submission time Handle Problem Language Result Execution time Memory
250980 2020-07-19T17:34:14 Z luciocf Park (BOI16_park) C++14
0 / 100
 346 ms 24056 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e3+10;
const int maxq = 1e5+10;


struct Query
{
	int r, e, ind;
} qry[maxq];

struct Tree
{
	int x, y, r;
} tree[maxn];

struct Par
{
	int u, v, k;
} par[maxn*maxn];

struct DSU
{
	int pai[maxn], peso[maxn];

	void init(int n)
	{
		for (int i = 1; i <= n; i++)
			pai[i] = i, peso[i] = 1;
	}

	int Find(int x)
	{
		if (pai[x] == x) return x;
		return pai[x] = Find(pai[x]);
	}

	void Join(int x, int y)
	{
		x = Find(x), y = Find(y);
		if (x == y) return;

		if (peso[x] < peso[y]) swap(x, y);

		pai[y] = x, peso[x] += peso[y];
	}
} dsu;

int n, m, w, h;
bool ans[maxq][5];

bool comp(Query a, Query b) {return a.r < b.r;}
bool comp2(Par a, Par b) {return a.k < b.k;}

ll dist(pii p1, pii p2)
{
	int d1 = p1.ff-p2.ff, d2 = p1.ss-p2.ss;

	return d1*d1 + d2*d2;
}

bool ok(int u, int v, int k, int q)
{
	if (q == 0)
	{
		ll d = dist({tree[u].x, tree[u].y}, {tree[v].x, tree[v].y});
		ll x = 1ll*(tree[u].r + tree[v].r + 2*k)*(tree[u].r + tree[v].r + 2*k);

		return (x >= d);
	}

	int d;

	if (v == n+4) d = tree[u].x;
	else if (v == n+1) d = tree[u].y;
	else if (v == n+2) d = w-tree[u].x;
	else d = h-tree[u].y;

	return (d <= tree[u].r+k);
}

int busca(int u, int v, int q)
{
	int ini = 0, fim = 1e9+10, ans = 1e9+10;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		if (ok(u, v, mid, q)) ans = mid, fim = mid-1;
		else ini = mid+1;
	}

	return ans;
}

int main(void)
{
	scanf("%d %d %d %d", &n, &m, &w, &h);

	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &tree[i].x, &tree[i].y, &tree[i].r);

	for (int i = 1; i <= m; i++)
	{
		scanf("%d %d", &qry[i].r, &qry[i].e);
		qry[i].ind = i;
	}

	int at = 0;

	for (int i = 1; i <= n; i++)
		for (int j = i+1; j <= n; j++)
			par[++at] = {i, j, busca(i, j, 0)};

	for (int i = 1; i <= n; i++)
		for (int j = n+1; j <= n+4; j++)
				par[++at] = {i, j, busca(i, j, 1)};

	sort(qry+1, qry+m+1, comp);
	sort(par+1, par+at+1, comp2);

	dsu.init(n+4);

	int ptr = 1;

	for (int i = 1; i <= m; i++)
	{
		int R = qry[i].r, ind = qry[i].ind;

		while (ptr <= at)
		{
			if (R >= par[ptr].k) dsu.Join(par[ptr].u, par[ptr].v), ++ptr;
			else break;
		}

		bool lig[5][5];

		for (int i = 1; i <= 4; i++)
			for (int j = 1; j <= 4; j++)
				lig[i][j] = (dsu.Find(n+i) == dsu.Find(n+j));

		if (qry[i].e == 1)
		{
			ans[ind][1] = 1;
			ans[ind][2] = (!lig[1][2] && !lig[1][3] && !lig[1][4]);
			ans[ind][3] = (!lig[2][3] && !lig[2][4] && !lig[1][3] && !lig[1][4]);
			ans[ind][4] = (!lig[1][4] && !lig[2][4] && !lig[3][4]);
		}
		else if (qry[i].e == 2)
		{
			ans[ind][1] = (!lig[1][2] && !lig[1][3] && !lig[1][4]);
			ans[ind][2] = 1;
			ans[ind][3] = (!lig[1][2] && !lig[2][3] && !lig[2][4]);
			ans[ind][4] = (!lig[1][2] && !lig[1][3] && !lig[2][4] && !lig[3][4]);
		}
		else if (qry[i].e == 3)
		{
			ans[ind][1] = (!lig[2][3] && !lig[2][4] && !lig[1][3] && !lig[1][4]);
			ans[ind][2] = (!lig[1][2] && !lig[2][3] && !lig[2][4]);
			ans[ind][3] = 1;
			ans[ind][4] = (!lig[1][3] && !lig[2][3] && !lig[3][4]);
		}
		else
		{
			ans[ind][1] = (!lig[1][4] && !lig[2][4] && !lig[3][4]);
			ans[ind][2] = (!lig[1][2] && !lig[1][3] && !lig[2][4] && !lig[3][4]);
			ans[ind][3] = (!lig[1][3] && !lig[2][3] && !lig[3][4]);
			ans[ind][4] = 1;
		}
	}

	for (int i = 1; i <= m; i++)
	{
		if (ans[i][1]) printf("1");
		if (ans[i][2]) printf("2");
		if (ans[i][3]) printf("3");
		if (ans[i][4]) printf("4");
		printf("\n");
	}
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d", &n, &m, &w, &h);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &tree[i].x, &tree[i].y, &tree[i].r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &qry[i].r, &qry[i].e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 24056 KB Output is correct
2 Incorrect 346 ms 24056 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 2556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 24056 KB Output is correct
2 Incorrect 346 ms 24056 KB Output isn't correct
3 Halted 0 ms 0 KB -