oj.uz

Submission #250998

# Submission time Handle Problem Language Result Execution time Memory
250998 2020-07-19T19:53:51 Z luciocf Park (BOI16_park) C++14
100 / 100
 702 ms 66424 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 = 3e3+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;
	long double 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;}

long double dist(pii p1, pii p2)
{
	long double d1 = p1.ff-p2.ff, d2 = p1.ss-p2.ss;
	return sqrt(d1*d1 + d2*d2);
}

long double dist_c(int u, int v, int q)
{
	if (q == 0)
	{
		long double d = dist({tree[u].x, tree[u].y}, {tree[v].x, tree[v].y});
		return (d - 1.0*tree[u].r - 1.0*tree[v].r);
	}

	long double 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;
}

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, dist_c(i, j, 0)};

	for (int i = 1; i <= n; i++)
		for (int j = n+1; j <= n+4; j++)
				par[++at] = {i, j, dist_c(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 (2.00*R > par[ptr].k) dsu.Join(par[ptr].u, par[ptr].v), ++ptr;
			else break;
		}

		bool lig[5][5];

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

		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:89: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:92: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:96: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
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 63352 KB Output is correct
2 Correct 605 ms 63248 KB Output is correct
3 Correct 624 ms 63224 KB Output is correct
4 Correct 608 ms 63224 KB Output is correct
5 Correct 602 ms 63248 KB Output is correct
6 Correct 637 ms 63224 KB Output is correct
7 Correct 590 ms 63352 KB Output is correct
8 Correct 600 ms 63224 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 2936 KB Output is correct
2 Correct 61 ms 2956 KB Output is correct
3 Correct 63 ms 3064 KB Output is correct
4 Correct 60 ms 3064 KB Output is correct
5 Correct 61 ms 2936 KB Output is correct
6 Correct 60 ms 3064 KB Output is correct
7 Correct 55 ms 2296 KB Output is correct
8 Correct 54 ms 3576 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 611 ms 63352 KB Output is correct
2 Correct 605 ms 63248 KB Output is correct
3 Correct 624 ms 63224 KB Output is correct
4 Correct 608 ms 63224 KB Output is correct
5 Correct 602 ms 63248 KB Output is correct
6 Correct 637 ms 63224 KB Output is correct
7 Correct 590 ms 63352 KB Output is correct
8 Correct 600 ms 63224 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 67 ms 2936 KB Output is correct
12 Correct 61 ms 2956 KB Output is correct
13 Correct 63 ms 3064 KB Output is correct
14 Correct 60 ms 3064 KB Output is correct
15 Correct 61 ms 2936 KB Output is correct
16 Correct 60 ms 3064 KB Output is correct
17 Correct 55 ms 2296 KB Output is correct
18 Correct 54 ms 3576 KB Output is correct
19 Correct 687 ms 66424 KB Output is correct
20 Correct 678 ms 66296 KB Output is correct
21 Correct 702 ms 66424 KB Output is correct
22 Correct 666 ms 66168 KB Output is correct
23 Correct 663 ms 66296 KB Output is correct
24 Correct 641 ms 66424 KB Output is correct