| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 321408 |
2020-11-12T09:39:01 Z |
Falcon |
Park (BOI16_park) |
C++17 |
|
571 ms |
94444 KB |
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); ++it)
#define rep(i, N) for(int i = 0; i < (N); ++i)
#define rrep(i, N) for(int i = (N) - 1; i >= 0; --i)
#define rep1(i, N) for(int i = 1; i <= (N); ++i)
#define rep2(i, s, e) for(int i = (s); i <= (e); ++i)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back
#ifdef DEBUG
#define debug(x...) { ++dbg::depth; string dbg_vals = dbg::to_string(x); --dbg::depth; dbg::fprint(__func__, __LINE__, #x, dbg_vals); }
#define light_debug(x) { dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0; }
#else
#define debug(x...) 42
#define light_debug(x) 42
#endif
template<typename T>
inline T& ckmin(T& a, T b) { return a = a > b ? b : a; }
template<typename T>
inline T& ckmax(T& a, T b) { return a = a < b ? b : a; }
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
class disjoint_set_union {
int n;
mutable vector<int> p;
private:
int root(int i) const {
return ~p[i] ? p[i] = root(p[i]) : i;
}
public:
disjoint_set_union(int n_) : n{n_}, p(n, -1) {};
void merge(int i, int j) {
i = root(i), j = root(j);
if(i != j) p[i] = j;
}
bool joined(int i, int j) const {
return root(i) == root(j);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifdef DEBUG
freopen("debug", "w", stderr);
#endif
int n, m, w, h; cin >> n >> m >> w >> h;
const int TOP = n, BTM = n + 1, LFT = n + 2, RGT = n + 3;
struct tree {
ll x, y, r;
};
vector<tree> trees(n);
for(auto& t : trees) cin >> t.x >> t.y >> t.r;
auto max_r = [](const tree& i, const tree& j) -> ll {
ll s = i.r + j.r;
ll dx = i.x - j.x, dy = i.y - j.y;
ll d = dx * dx + dy * dy;
if(s * s > d) return -1;
// We need (2r + i.r + j.r) ^ 2 <= d
ll r = 0;
for(ll k = 1LL << 28; k; k >>= 1) {
ll tmp = (r + k) * 2 + s;
if(tmp * tmp <= d) r += k;
}
return r;
};
vector<array<ll, 3>> tree_pairs; tree_pairs.reserve(n * (n - 1) / 2);
rep(i, n)
rep2(j, i + 1, n - 1)
tree_pairs.pb({max_r(trees[i], trees[j]), i, j});
rep(i, n) {
auto t = trees[i]; debug(t.x, t.y, t.r);
tree_pairs.pb({(t.x - t.r) / 2, i, LFT});
tree_pairs.pb({(t.y - t.r) / 2, i, BTM});
tree_pairs.pb({(w - t.x - t.r) / 2, i, RGT});
tree_pairs.pb({(h - t.y - t.r) / 2, i, TOP});
}
sort(all(tree_pairs));
debug(tree_pairs);
vector<array<int, 3>> queries(m); // {r, e, i}
rep(i, m) cin >> queries[i][0] >> queries[i][1], queries[i][2] = i;
sort(all(queries));
disjoint_set_union dsu(n + 4);
vector<string> ans(m);
auto tp = tree_pairs.begin();
for(const auto& q : queries) {
while(tp != tree_pairs.end()) {
auto p = *tp;
if(p[0] < q[0])
dsu.merge(p[1], p[2]);
else
break;
++tp;
}
switch(q[1]) {
case 1: // Bottom Left
ans[q[2]].pb('1');
if(!dsu.joined(BTM, TOP)
&& !dsu.joined(BTM, LFT)
&& !dsu.joined(BTM, RGT))
ans[q[2]].pb('2');
if(!dsu.joined(BTM, TOP)
&& !dsu.joined(BTM, LFT)
&& !dsu.joined(TOP, RGT)
&& !dsu.joined(LFT, RGT))
ans[q[2]].pb('3');
if(!dsu.joined(BTM, LFT)
&& !dsu.joined(LFT, RGT)
&& !dsu.joined(TOP, LFT))
ans[q[2]].pb('4');
break;
case 2: // Bottom right
if(!dsu.joined(BTM, TOP)
&& !dsu.joined(BTM, LFT)
&& !dsu.joined(BTM, RGT))
ans[q[2]].pb('1');
ans[q[2]].pb('2');
if(!dsu.joined(BTM, RGT)
&& !dsu.joined(TOP, RGT)
&& !dsu.joined(LFT, RGT))
ans[q[2]].pb('3');
if(!dsu.joined(BTM, RGT)
&& !dsu.joined(LFT, RGT)
&& !dsu.joined(TOP, BTM)
&& !dsu.joined(LFT, TOP))
ans[q[2]].pb('4');
break;
case 3: // Top right
if(!dsu.joined(BTM, TOP)
&& !dsu.joined(BTM, LFT)
&& !dsu.joined(TOP, RGT)
&& !dsu.joined(LFT, RGT))
ans[q[2]].pb('1');
if(!dsu.joined(BTM, RGT)
&& !dsu.joined(TOP, RGT)
&& !dsu.joined(LFT, RGT))
ans[q[2]].pb('2');
ans[q[2]].pb('3');
if(!dsu.joined(BTM, TOP)
&& !dsu.joined(TOP, LFT)
&& !dsu.joined(TOP, RGT))
ans[q[2]].pb('4');
break;
case 4: // Top left
if(!dsu.joined(BTM, LFT)
&& !dsu.joined(LFT, RGT)
&& !dsu.joined(TOP, LFT))
ans[q[2]].pb('1');
if(!dsu.joined(BTM, RGT)
&& !dsu.joined(LFT, RGT)
&& !dsu.joined(TOP, BTM)
&& !dsu.joined(LFT, TOP))
ans[q[2]].pb('2');
if(!dsu.joined(BTM, TOP)
&& !dsu.joined(TOP, LFT)
&& !dsu.joined(TOP, RGT))
ans[q[2]].pb('3');
ans[q[w]].pb('4');
break;
}
debug(q, ans[q[2]]);
}
for(auto& s : ans) cout << s << '\n';
#ifdef DEBUG
dbg::dout << "\nExecution time: " << clock() << "ms\n";
#endif
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:26:29: warning: statement has no effect [-Wunused-value]
26 | #define debug(x...) 42
| ^~
park.cpp:104:28: note: in expansion of macro 'debug'
104 | auto t = trees[i]; debug(t.x, t.y, t.r);
| ^~~~~
park.cpp:26:29: warning: statement has no effect [-Wunused-value]
26 | #define debug(x...) 42
| ^~
park.cpp:112:5: note: in expansion of macro 'debug'
112 | debug(tree_pairs);
| ^~~~~
park.cpp:26:29: warning: statement has no effect [-Wunused-value]
26 | #define debug(x...) 42
| ^~
park.cpp:201:9: note: in expansion of macro 'debug'
201 | debug(q, ans[q[2]]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
520 ms |
94384 KB |
Output is correct |
| 2 |
Correct |
513 ms |
94444 KB |
Output is correct |
| 3 |
Correct |
503 ms |
94316 KB |
Output is correct |
| 4 |
Correct |
531 ms |
94316 KB |
Output is correct |
| 5 |
Correct |
561 ms |
94336 KB |
Output is correct |
| 6 |
Correct |
571 ms |
94368 KB |
Output is correct |
| 7 |
Correct |
510 ms |
94332 KB |
Output is correct |
| 8 |
Correct |
523 ms |
94444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
11280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
520 ms |
94384 KB |
Output is correct |
| 2 |
Correct |
513 ms |
94444 KB |
Output is correct |
| 3 |
Correct |
503 ms |
94316 KB |
Output is correct |
| 4 |
Correct |
531 ms |
94316 KB |
Output is correct |
| 5 |
Correct |
561 ms |
94336 KB |
Output is correct |
| 6 |
Correct |
571 ms |
94368 KB |
Output is correct |
| 7 |
Correct |
510 ms |
94332 KB |
Output is correct |
| 8 |
Correct |
523 ms |
94444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Runtime error |
50 ms |
11280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
