Submission #114410

#	Time	Username	Problem	Language	Result	Execution time	Memory
114410		atoiz	Park (BOI16_park)	C++14	27 / 100	331 ms	63336 KiB

park

/*input
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

const int MAXN = 2010, SZ = MAXN + 10;
int N, M;
long long W, H, X[MAXN], Y[MAXN], R[MAXN];
bool conn[4][4], ans[MAXN][4];
int prv(int u) { return (--u < 0 ? u + 4 : u); }
int nxt(int u) { return (++u > 3 ? u - 4 : u); }
void disc(int u, int v) { conn[u][v] = conn[v][u] = 0; }
long long sqr(long long x) { return x * x; }

int dsu[SZ], sz[SZ];
void init() { for (int i = 0; i < SZ; ++i) dsu[i] = i, sz[i] = 1; }
int get(int u) { return (dsu[u] == u ? u : dsu[u] = get(dsu[u])); }
bool same(int u, int v) { return get(u) == get(v); }
void join(int u, int v) { u = get(u), v = get(v); if (u == v) return; if (sz[u] < sz[v]) swap(u, v); sz[u] += sz[v]; dsu[v] = u; }

#define FOR(i, a, b) for (int i = a; i <= b; ++i)

struct Event
{
	char type;
	long long w;

	int u, v;
	void add(int _u, int _v, long long _w) { type = 'a', u = _u, v = _v; w = _w; }

	int corner, id;
	void query(int _corner, int _id, long long _w) { type = 'q', corner = _corner, id = _id, w = _w; }

	void work()
	{
		// cout << type << ' ';
		// if (type == 'a') cout << u << ' ' << v << endl;
		// else cout << corner << ' ' << id + 1 << endl;

		if (type == 'a') join(u, v);
		else {
			FOR(i, 0, 3) FOR(j, 0, 3) conn[i][j] = 1;
			FOR(i, 0, 3) if (same(MAXN + prv(i), MAXN + i)) FOR(j, 0, 3) disc(i, j);
			if (same(MAXN + 0, MAXN + 2)) disc(0, 1), disc(0, 2), disc(3, 1), disc(3, 2);
			if (same(MAXN + 1, MAXN + 3)) disc(0, 2), disc(0, 3), disc(1, 2), disc(1, 3);
			FOR(i, 0, 3) conn[i][i] = 1;
			FOR(i, 0, 3) ans[id][i] = conn[corner][i];
		}
	}

	bool operator< (const Event &e)
	{
		return (w == e.w ? type > e.type : w < e.w);
	}
} events[MAXN * MAXN * 2];
int noEvents = 0;

int main()
{
	init();
	scanf("%d %d", &N, &M);
	scanf("%lld %lld", &W, &H);
	for (int i = 0; i < N; ++i) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);

	for (int i = 0; i < N; ++i) {
		events[noEvents++].add(i, MAXN + 0, Y[i] - R[i]);
		events[noEvents++].add(i, MAXN + 1, W - X[i] - R[i]);
		events[noEvents++].add(i, MAXN + 2, H - Y[i] - R[i]);
		events[noEvents++].add(i, MAXN + 3, X[i] - R[i]);
	}
	for (int i = 0; i < N; ++i) for (int j = i + 1; j < N; ++j) {
		long long w = sqrtl(sqr(X[i] - X[j]) + sqr(Y[i] - Y[j]));
		w -= R[i] + R[j];
		events[noEvents++].add(i, j, w);
	}
	for (int id = 0; id < M; ++id) {
		int r, e;
		scanf("%d %d", &r, &e);
		events[noEvents++].query(e - 1, id, r * 2);
	}

	sort(events, events + noEvents);
	for (int i = 0; i < noEvents; ++i) events[i].work();
	for (int id = 0; id < M; ++id) {
		for (int i = 0; i < 4; ++i) if (ans[id][i]) putchar('1' + i);
		putchar('\n');
	}
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
park.cpp:80:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &W, &H);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
park.cpp:81:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; ++i) scanf("%lld %lld %lld", &X[i], &Y[i], &R[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &r, &e);
   ~~~~~^~~~~~~~~~~~~~~~~

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