| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 231033 |
2020-05-12T11:58:57 Z |
islingr |
Park (BOI16_park) |
C++14 |
|
654 ms |
70332 KB |
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#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 rall(x) (x).rbegin(), (x).rend()
#define eb(x...) emplace_back(x)
#define f first
#define s second
ld eps = 1e-6;
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(u, 0, n + 4) nxt[u] = -1;
rep(i, 0, m) {
cin >> v[i].r >> v[i].c; --v[i].c;
v[i].i = i;
}
sort(v, v + m);
rep(i, 0, m) {
while (!q.empty() && (q.back().f < 2 * v[i].r || abs(q.back().f - 2 * v[i].r) <= eps)) {
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';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
639 ms |
70300 KB |
Output is correct |
| 2 |
Correct |
640 ms |
70296 KB |
Output is correct |
| 3 |
Correct |
645 ms |
70300 KB |
Output is correct |
| 4 |
Correct |
654 ms |
70300 KB |
Output is correct |
| 5 |
Correct |
642 ms |
70316 KB |
Output is correct |
| 6 |
Correct |
645 ms |
70300 KB |
Output is correct |
| 7 |
Correct |
542 ms |
70332 KB |
Output is correct |
| 8 |
Incorrect |
530 ms |
70300 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
6896 KB |
Output is correct |
| 2 |
Correct |
61 ms |
6764 KB |
Output is correct |
| 3 |
Correct |
60 ms |
6768 KB |
Output is correct |
| 4 |
Correct |
61 ms |
6736 KB |
Output is correct |
| 5 |
Correct |
63 ms |
6760 KB |
Output is correct |
| 6 |
Incorrect |
59 ms |
6896 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
639 ms |
70300 KB |
Output is correct |
| 2 |
Correct |
640 ms |
70296 KB |
Output is correct |
| 3 |
Correct |
645 ms |
70300 KB |
Output is correct |
| 4 |
Correct |
654 ms |
70300 KB |
Output is correct |
| 5 |
Correct |
642 ms |
70316 KB |
Output is correct |
| 6 |
Correct |
645 ms |
70300 KB |
Output is correct |
| 7 |
Correct |
542 ms |
70332 KB |
Output is correct |
| 8 |
Incorrect |
530 ms |
70300 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
