oj.uz

Submission #231041

# Submission time Handle Problem Language Result Execution time Memory
231041 2020-05-12T12:29:05 Z islingr Park (BOI16_park) C++14
100 / 100
 692 ms 70772 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
 
ld abs(point p) { return hypot(ld(real(p)), ld(imag(p))); }
struct event {
	int r, c, i;
	bool operator<(const event &e) { return r < e.r; } 
};

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<ld, 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 642 ms 70304 KB Output is correct
2 Correct 644 ms 70304 KB Output is correct
3 Correct 640 ms 70300 KB Output is correct
4 Correct 650 ms 70304 KB Output is correct
5 Correct 637 ms 70300 KB Output is correct
6 Correct 647 ms 70484 KB Output is correct
7 Correct 536 ms 70304 KB Output is correct
8 Correct 518 ms 70300 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 61 ms 6764 KB Output is correct
2 Correct 61 ms 6768 KB Output is correct
3 Correct 61 ms 6764 KB Output is correct
4 Correct 63 ms 6896 KB Output is correct
5 Correct 61 ms 6768 KB Output is correct
6 Correct 58 ms 7024 KB Output is correct
7 Correct 55 ms 7160 KB Output is correct
8 Correct 65 ms 7160 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 70304 KB Output is correct
2 Correct 644 ms 70304 KB Output is correct
3 Correct 640 ms 70300 KB Output is correct
4 Correct 650 ms 70304 KB Output is correct
5 Correct 637 ms 70300 KB Output is correct
6 Correct 647 ms 70484 KB Output is correct
7 Correct 536 ms 70304 KB Output is correct
8 Correct 518 ms 70300 KB Output is correct
9 Correct 7 ms 4480 KB Output is correct
10 Correct 7 ms 4480 KB Output is correct
11 Correct 61 ms 6764 KB Output is correct
12 Correct 61 ms 6768 KB Output is correct
13 Correct 61 ms 6764 KB Output is correct
14 Correct 63 ms 6896 KB Output is correct
15 Correct 61 ms 6768 KB Output is correct
16 Correct 58 ms 7024 KB Output is correct
17 Correct 55 ms 7160 KB Output is correct
18 Correct 65 ms 7160 KB Output is correct
19 Correct 691 ms 70772 KB Output is correct
20 Correct 681 ms 70556 KB Output is correct
21 Correct 682 ms 70688 KB Output is correct
22 Correct 670 ms 70556 KB Output is correct
23 Correct 692 ms 70556 KB Output is correct
24 Correct 580 ms 70556 KB Output is correct