| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 231019 |
2020-05-12T11:37:17 Z |
islingr |
Park (BOI16_park) |
C++14 |
|
914 ms |
70484 KB |
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
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';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
331 ms |
70300 KB |
Output is correct |
| 2 |
Correct |
335 ms |
70300 KB |
Output is correct |
| 3 |
Correct |
333 ms |
70288 KB |
Output is correct |
| 4 |
Correct |
333 ms |
70300 KB |
Output is correct |
| 5 |
Correct |
329 ms |
70484 KB |
Output is correct |
| 6 |
Correct |
331 ms |
70304 KB |
Output is correct |
| 7 |
Correct |
914 ms |
70276 KB |
Output is correct |
| 8 |
Incorrect |
235 ms |
70432 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
6768 KB |
Output is correct |
| 2 |
Correct |
67 ms |
7792 KB |
Output is correct |
| 3 |
Correct |
63 ms |
7916 KB |
Output is correct |
| 4 |
Correct |
62 ms |
7792 KB |
Output is correct |
| 5 |
Correct |
61 ms |
7920 KB |
Output is correct |
| 6 |
Incorrect |
65 ms |
7920 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
331 ms |
70300 KB |
Output is correct |
| 2 |
Correct |
335 ms |
70300 KB |
Output is correct |
| 3 |
Correct |
333 ms |
70288 KB |
Output is correct |
| 4 |
Correct |
333 ms |
70300 KB |
Output is correct |
| 5 |
Correct |
329 ms |
70484 KB |
Output is correct |
| 6 |
Correct |
331 ms |
70304 KB |
Output is correct |
| 7 |
Correct |
914 ms |
70276 KB |
Output is correct |
| 8 |
Incorrect |
235 ms |
70432 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
