| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1096482 |
2024-10-04T15:02:43 Z |
KickingKun |
Park (BOI16_park) |
C++17 |
|
193 ms |
49828 KB |
// PHK
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define bigint __int128
#define emb emplace_back
#define pb push_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define Task ""
#define MASK(k) (1ull << k)
#define bitcnt(k) __builtin_popcount(k)
#define testBit(n, k) ((n >> k) & 1)
#define flipBit(n, k) (n ^ (1ll << k))
#define offBit(n, k) (n & ~MASK(k))
#define onBit(n, k) (n | (1ll << k))
#define lowBit(k) (31 - __builtin_clz(k & -k))
template <class T> bool minimize(T &a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool maximize(T &a, T b) {if (a < b) {a = b; return true;} return false;}
const int N = 2e3 + 10, lim = 1e5 + 2, mod = 1e9 + 7;
const ll INF = 1e18;
// BOI 2016
#define int ll
struct Edge {
int u, v, d;
Edge () {}
Edge (int _u, int _v, int _d) {
u = _u; v = _v; d = _d;
}
bool operator < (const Edge &other) {
return d < other.d;
}
};
struct Circle {
int x, y, r;
ll dis(const Circle &b) {
return 1ll * (x - b.x) * (x - b.x) + 1ll * (y - b.y) * (y - b.y);
}
} cir[N];
struct Query {
int r, e, id;
Query () {}
Query (int _r, int _e, int _id) {
r = _r; e = _e; id = _id;
}
bool operator < (const Query &other) {
return r < other.r;
}
};
struct DSU {
vector <int> par, sz;
DSU (int n) {
par.assign(n + 1, 0); sz.assign(n + 1, 1);
}
int find_set(int u) {
return par[u] ? par[u] = find_set(par[u]) : u;
}
bool unite(int u, int v) {
u = find_set(u); v = find_set(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
sz[par[v] = u] += sz[v];
return true;
}
bool same_set(int u, int v) {
return find_set(u) == find_set(v);
}
};
int n, m, w, h;
vector <Edge> edge;
vector <Query> que;
bool reach[lim][5], canGo[5][5];
main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
if (fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
// n + 1, n + 2, n + 3, n + 4: top, left, bottom, right border
auto square = [&] (ll x) {
return x * x;
};
cin >> n >> m >> w >> h;
for (int i = 1; i <= n; i++) {
cin >> cir[i].x >> cir[i].y >> cir[i].r;
for (int j = 1; j < i; j++) {
ll dist = ceil(cir[i].dis(cir[j])) - cir[i].r - cir[j].r;
edge.emb(i, j, dist);
}
edge.emb(n + 1, i, square(h - cir[i].y - cir[i].r));
edge.emb(n + 2, i, square(cir[i].x - cir[i].r));
edge.emb(n + 3, i, square(cir[i].y - cir[i].r));
edge.emb(n + 4, i, square(w - cir[i].x - cir[i].r));
}
sort (all(edge));
for (int i = 0; i < m; i++) {
int r, e; cin >> r >> e;
que.emb(r, e, i);
}
sort (all(que));
int p = -1; DSU dsu(n + 4);
for (auto [r, e, id]: que) {
while (p + 1 < edge.size() && edge[p + 1].d <= 4ll * r * r) {
++p; dsu.unite(edge[p].u, edge[p].v);
// cout << edge[p].u << ' ' << edge[p].v << '\n';
}
// 4 3
// 1 2
memset(canGo, true, sizeof canGo);
if (dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 2, n + 3) || dsu.same_set(n + 3, n + 4))
canGo[1][2] = false;
if (dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 2, n + 3) || dsu.same_set(n + 1, n + 4))
canGo[1][3] = false;
if (dsu.same_set(n + 1, n + 2) || dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 2, n + 3))
canGo[1][4] = false;
if (dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 1, n + 4) || dsu.same_set(n + 3, n + 4))
canGo[2][3] = false;
if (dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 2, n + 4) || dsu.same_set(n + 1, n + 2) || dsu.same_set(n + 3, n + 4))
canGo[2][4] = false;
if (dsu.same_set(n + 1, n + 2) || dsu.same_set(n + 1, n + 3) || dsu.same_set(n + 1, n + 4))
canGo[3][4] = false;
for (int i = 1; i <= 4; i++)
reach[id][i] = canGo[min(i, e)][max(i, e)];
}
for (int i = 0; i < m; i++) {
string res;
for (int x = 1; x <= 4; x++)
if (reach[i][x]) res += char(x + 48);
cout << res << '\n';
}
}
Compilation message
park.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
89 | main() {
| ^~~~
park.cpp: In function 'int main()':
park.cpp:125:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | while (p + 1 < edge.size() && edge[p + 1].d <= 4ll * r * r) {
| ~~~~~~^~~~~~~~~~~~~
park.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | freopen(Task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | freopen(Task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
49828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
49828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
