oj.uz

Submission #231048

# Submission time Handle Problem Language Result Execution time Memory
231048 2020-05-12T12:41:42 Z islingr Park (BOI16_park) C++14
100 / 100
 379 ms 29996 KB 
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
using namespace std;

using ld = long double;
using point = complex<int>;
using pii = pair<int, int>;
 
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define eb(x...) emplace_back(x)
 
#define f first
#define s second
 
struct event {
	int r, c, i;
	bool operator<(const event &e) { return r < e.r; } 
};

int abs(const point &p) { return floor(hypot(real(p), imag(p))); }
constexpr int N = 1 << 11, M = 1 << 17;
int nxt[N], rnk[N], r[N], n, m, w, h;
point p[N];
event v[M];
string ans[M];
vector<pair<int, pii>> q;
vector<pii> c[4][4] = {
		{{}, {{1, 3}, {1, 0}, {1, 2}}, {{1, 0}, {1, 3}, {2, 0}, {2, 3}}, {{0, 1}, {0, 2}, {0, 3}}},
		{{{1, 3}, {1, 0}, {1, 2}}, {}, {{2, 1}, {2, 0}, {2, 3}}, {{1, 2}, {1, 3}, {0, 2}, {0, 3}}},
		{{{2, 3}, {0, 1}, {1, 3}, {0, 2}}, {{0, 2}, {1, 2}, {2, 3}}, {}, {{1, 3}, {2, 3}, {0, 3}}},
		{{{0, 3}, {0, 2}, {0, 1}}, {{3, 0}, {3, 1}, {2, 0}, {2, 1}}, {{1, 3}, {0, 3}, {2, 3}}, {}}
	};

int head(int u) { return nxt[u] != -1 ? nxt[u] = head(nxt[u]) : u; }
void unite(int u, int v) {
	u = head(u); v = head(v);
	if (u == v) return;
	if (rnk[u] < rnk[v]) nxt[u] = v;
	else {
		nxt[v] = u;
		if (rnk[u] == rnk[v]) ++rnk[u];
	}
}
bool same(int u, int v) { return head(u) == head(v); }
void unite(pii p) { unite(p.f, p.s); }

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	cin >> n >> m >> w >> h;
	rep(i, 0, n) {
		int x, y; cin >> x >> y >> r[i];
		p[i] = {x, y};
	}

	rep(i, 0, n) {
		int x = real(p[i]), y = imag(p[i]);
		q.eb(x - r[i], pii(i, n));
		q.eb(y - r[i], pii(i, n + 1));
		q.eb(w - x - r[i], pii(i, n + 2));
		q.eb(h - y - r[i], pii(i, n + 3));
	}
	rep(i, 0, n) rep(j, i + 1, n) q.eb(abs(p[i] - p[j]) - r[i] - r[j], pii(i, j));
	sort(rall(q));

	rep(i, 0, m) {
		cin >> v[i].r >> v[i].c; --v[i].c;
		v[i].i = i;
	}
	sort(v, v + m);
 
	rep(u, 0, n + 4) nxt[u] = -1;
	rep(i, 0, m) {
		while (!q.empty() && q.back().f < 2 * v[i].r) {
			unite(q.back().s); q.pop_back();
		}
		rep(j, 0, 4) {
			bool works = true;
			trav(x, c[v[i].c][j])
				if (same(x.f + n, x.s + n))
					works = false;
			if (works) ans[v[i].i] += '1' + j;
		}
	}
 
	rep(i, 0, m) cout << ans[i] << '\n';
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 29256 KB Output is correct
2 Correct 334 ms 29268 KB Output is correct
3 Correct 323 ms 29256 KB Output is correct
4 Correct 327 ms 29256 KB Output is correct
5 Correct 327 ms 29256 KB Output is correct
6 Correct 332 ms 29256 KB Output is correct
7 Correct 276 ms 29276 KB Output is correct
8 Correct 264 ms 29268 KB Output is correct
9 Correct 7 ms 4480 KB Output is correct
10 Correct 7 ms 4480 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 6388 KB Output is correct
2 Correct 58 ms 6388 KB Output is correct
3 Correct 65 ms 6384 KB Output is correct
4 Correct 59 ms 6388 KB Output is correct
5 Correct 61 ms 6332 KB Output is correct
6 Correct 55 ms 6644 KB Output is correct
7 Correct 56 ms 6136 KB Output is correct
8 Correct 55 ms 6008 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 29256 KB Output is correct
2 Correct 334 ms 29268 KB Output is correct
3 Correct 323 ms 29256 KB Output is correct
4 Correct 327 ms 29256 KB Output is correct
5 Correct 327 ms 29256 KB Output is correct
6 Correct 332 ms 29256 KB Output is correct
7 Correct 276 ms 29276 KB Output is correct
8 Correct 264 ms 29268 KB Output is correct
9 Correct 7 ms 4480 KB Output is correct
10 Correct 7 ms 4480 KB Output is correct
11 Correct 60 ms 6388 KB Output is correct
12 Correct 58 ms 6388 KB Output is correct
13 Correct 65 ms 6384 KB Output is correct
14 Correct 59 ms 6388 KB Output is correct
15 Correct 61 ms 6332 KB Output is correct
16 Correct 55 ms 6644 KB Output is correct
17 Correct 56 ms 6136 KB Output is correct
18 Correct 55 ms 6008 KB Output is correct
19 Correct 379 ms 29996 KB Output is correct
20 Correct 372 ms 29896 KB Output is correct
21 Correct 376 ms 29996 KB Output is correct
22 Correct 366 ms 29872 KB Output is correct
23 Correct 377 ms 29868 KB Output is correct
24 Correct 318 ms 29996 KB Output is correct