oj.uz

답안 #231020

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
231020 2020-05-12T11:38:11 Z islingr Park (BOI16_park) C++14
0 / 100
 952 ms 70416 KB 
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define int ll

using ll = long long;
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 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 vis[M];
string ans[M];

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};
	}
	priority_queue<pair<ld, pii>, vector<pair<ld, pii>>, greater<pair<ld, pii>>> q;
	rep(i, 0, n) {
		int x = real(p[i]), y = imag(p[i]);
		q.push({x - r[i], {i, n}});
		q.push({y - r[i], {i, n + 1}});
		q.push({w - x - r[i], {i, n + 2}});
		q.push({h - y - r[i], {i, n + 3}});
	}
	rep(i, 0, n) rep(j, i + 1, n) q.push({abs(p[i] - p[j]) - r[i] - r[j], {i, j}});
	rep(u, 0, n + 4) nxt[u] = -1;
	rep(v, 0, m) {
		cin >> vis[v].r >> vis[v].c; --vis[v].c;
		vis[v].i = v;
	}
	sort(vis, vis + m);

	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}}, {}}
	};
	rep(i, 0, m) {
		while (!q.empty() && q.top().f <= 2 * vis[i].r) {
			unite(q.top().s); q.pop();
		}
		rep(j, 0, 4) {
			bool works = true;
			trav(v, c[vis[i].c][j])
				if (same(v.f + n, v.s + n))
					works = false;
			if (works) ans[vis[i].i] += '1' + j;
		}
	}
	rep(i, 0, m) cout << ans[i] << '\n';
}

Subtask #1
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 70300 KB Output is correct
2 Correct 340 ms 70276 KB Output is correct
3 Correct 344 ms 70300 KB Output is correct
4 Correct 341 ms 70304 KB Output is correct
5 Correct 334 ms 70300 KB Output is correct
6 Correct 338 ms 70416 KB Output is correct
7 Correct 952 ms 70300 KB Output is correct
8 Incorrect 237 ms 70300 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 8048 KB Output is correct
2 Correct 62 ms 8048 KB Output is correct
3 Correct 61 ms 7928 KB Output is correct
4 Correct 57 ms 7920 KB Output is correct
5 Correct 57 ms 8048 KB Output is correct
6 Incorrect 59 ms 8044 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 70300 KB Output is correct
2 Correct 340 ms 70276 KB Output is correct
3 Correct 344 ms 70300 KB Output is correct
4 Correct 341 ms 70304 KB Output is correct
5 Correct 334 ms 70300 KB Output is correct
6 Correct 338 ms 70416 KB Output is correct
7 Correct 952 ms 70300 KB Output is correct
8 Incorrect 237 ms 70300 KB Output isn't correct
9 Halted 0 ms 0 KB -