oj.uz

Submission #114411

# Submission time Handle Problem Language Result Execution time Memory
114411 2019-06-01T08:47:52 Z atoiz Park (BOI16_park) C++14
100 / 100
 372 ms 68244 KB 
/*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, MAXM = 100007;
int N, M;
long long W, H, X[MAXN], Y[MAXN], R[MAXN];
bool conn[4][4], ans[MAXM][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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 63252 KB Output is correct
2 Correct 325 ms 63280 KB Output is correct
3 Correct 323 ms 63276 KB Output is correct
4 Correct 318 ms 63272 KB Output is correct
5 Correct 337 ms 63244 KB Output is correct
6 Correct 327 ms 63300 KB Output is correct
7 Correct 301 ms 63280 KB Output is correct
8 Correct 306 ms 63272 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4948 KB Output is correct
2 Correct 46 ms 5972 KB Output is correct
3 Correct 45 ms 5860 KB Output is correct
4 Correct 45 ms 5924 KB Output is correct
5 Correct 43 ms 5968 KB Output is correct
6 Correct 42 ms 5904 KB Output is correct
7 Correct 40 ms 5368 KB Output is correct
8 Correct 42 ms 5368 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 63252 KB Output is correct
2 Correct 325 ms 63280 KB Output is correct
3 Correct 323 ms 63276 KB Output is correct
4 Correct 318 ms 63272 KB Output is correct
5 Correct 337 ms 63244 KB Output is correct
6 Correct 327 ms 63300 KB Output is correct
7 Correct 301 ms 63280 KB Output is correct
8 Correct 306 ms 63272 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 46 ms 4948 KB Output is correct
12 Correct 46 ms 5972 KB Output is correct
13 Correct 45 ms 5860 KB Output is correct
14 Correct 45 ms 5924 KB Output is correct
15 Correct 43 ms 5968 KB Output is correct
16 Correct 42 ms 5904 KB Output is correct
17 Correct 40 ms 5368 KB Output is correct
18 Correct 42 ms 5368 KB Output is correct
19 Correct 360 ms 68240 KB Output is correct
20 Correct 357 ms 68104 KB Output is correct
21 Correct 362 ms 68204 KB Output is correct
22 Correct 369 ms 68136 KB Output is correct
23 Correct 372 ms 68100 KB Output is correct
24 Correct 365 ms 68244 KB Output is correct