| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 514133 |
2022-01-18T04:18:12 Z |
sberens |
Park (BOI16_park) |
C++17 |
|
505 ms |
71280 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)
template<typename T, unsigned long N>
istream & operator>>(istream& in, array<T, N>& arr) {
F0R(i, N) in >> arr[i];
return in;
}
using ll = long long;
using ld = long double;
template<typename T>
using vv = vector<vector<T>>;
using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;
using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;
template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;
template<typename T>
using oset = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
const ll M = 1000000007;
const ll infll = M * M;
struct dsu {
vector<int> p, sz;
explicit dsu(int n) : p(n), sz(n, 1) {
iota(p.begin(), p.end(), 0);
}
int rep(int x) {
while (x != p[x]) x = p[x] = p[p[x]];
return x;
}
// returns true if a and b are in the same set, and then unites them.
bool unite(int a, int b) {
a = rep(a), b = rep(b);
if (sz[a] < sz[b]) swap(a, b);
if (a != b) {
p[b] = a;
sz[a] += sz[b];
}
return a == b;
}
// returns true if a and b are in the same set.
bool query(int a, int b) {
return rep(a) == rep(b);
}
// returns the size of the set containing x
int size(int x) {
return sz[rep(x)];
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, w, h;
cin >> n >> m >> w >> h;
vector<array<int, 3>> trees(n);
F0R(i, n) cin >> trees[i];
vector<array<int, 3>> visitors(m);
F0R(i, m) {
cin >> visitors[i][0] >> visitors[i][1];
visitors[i][2] = i;
}
vector<tuple<ld, int, int>> edges;
const int L = n, T = n+1, R = n+2, B = n+3;
F0R(i, n) {
auto[x1, y1, r1] = trees[i];
FOR(j, i+1, n){
auto[x2, y2, r2] = trees[j];
edges.eb(sqrt(pow((ld)x1-x2,2) + pow((ld)y1-y2,2)) -r1 -r2, i, j);
}
edges.eb(x1-r1, L, i);
edges.eb(y1-r1, T, i);
edges.eb(w-(x1+r1), R, i);
edges.eb(h-(y1+r1), B, i);
}
sort(all(edges));
sort(all(visitors));
int ce = 0;
dsu d(n+4);
set<int> disc;
auto has_any = [&](vi v) -> bool {
for (int x : v) if (disc.count(x) == 1) return true;
return false;
};
vvi res(m);
for (auto [r, e, resi] : visitors) {
while (ce < edges.size() && get<0>(edges[ce]) < 2 * r) {
d.unite(get<1>(edges[ce]), get<2>(edges[ce]));
++ce;
}
if (d.query(L, T)) disc.insert(0);
if (d.query(T, R)) disc.insert(1);
if (d.query(R, B)) disc.insert(2);
if (d.query(B, L)) disc.insert(3);
if (d.query(L, R)) disc.insert(4);
if (d.query(T, B)) disc.insert(5);
if (e == 1) {
res[resi].pb(1);
if (!has_any({0,1,5})) res[resi].pb(2);
if (!has_any({0,2,4,5})) res[resi].pb(3);
if (!has_any({0, 4, 3})) res[resi].pb(4);
} else if (e == 4) {
if (!has_any({0,3,4})) res[resi].pb(1);
if (!has_any({4,5,1,3})) res[resi].pb(2);
if (!has_any({3,2,5})) res[resi].pb(3);
res[resi].pb(4);
} else if (e == 3) {
if (!has_any({0,2,4,5})) res[resi].pb(1);
if (!has_any({2,1,4})) res[resi].pb(2);
res[resi].pb(3);
if (!has_any({2,3,5})) res[resi].pb(4);
}else if (e == 2) {
if (!has_any({0,1,5})) res[resi].pb(1);
res[resi].pb(2);
if (!has_any({1,2,4})) res[resi].pb(3);
if (!has_any({4,5,1,3})) res[resi].pb(4);
}
}
F0R(i, m) {
for (int x : res[i]) cout << x;
cout << '\n';
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long double, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | while (ce < edges.size() && get<0>(edges[ce]) < 2 * r) {
| ~~~^~~~~~~~~~~~~~
park.cpp: In instantiation of 'std::istream& operator>>(std::istream&, std::array<_Tp, _Nm>&) [with T = int; long unsigned int N = 3; std::istream = std::basic_istream<char>]':
park.cpp:97:29: required from here
park.cpp:18:42: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
18 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
| ^
park.cpp:19:19: note: in expansion of macro 'FOR'
19 | #define F0R(i, a) FOR(i,0,a)
| ^~~
park.cpp:25:5: note: in expansion of macro 'F0R'
25 | F0R(i, N) in >> arr[i];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
439 ms |
66132 KB |
Output is correct |
| 2 |
Correct |
423 ms |
66024 KB |
Output is correct |
| 3 |
Correct |
430 ms |
66144 KB |
Output is correct |
| 4 |
Correct |
432 ms |
66120 KB |
Output is correct |
| 5 |
Correct |
430 ms |
66156 KB |
Output is correct |
| 6 |
Correct |
429 ms |
66232 KB |
Output is correct |
| 7 |
Correct |
419 ms |
66152 KB |
Output is correct |
| 8 |
Correct |
407 ms |
66168 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
7908 KB |
Output is correct |
| 2 |
Correct |
88 ms |
9000 KB |
Output is correct |
| 3 |
Correct |
64 ms |
8880 KB |
Output is correct |
| 4 |
Correct |
76 ms |
9020 KB |
Output is correct |
| 5 |
Correct |
70 ms |
8976 KB |
Output is correct |
| 6 |
Correct |
70 ms |
9016 KB |
Output is correct |
| 7 |
Correct |
70 ms |
8544 KB |
Output is correct |
| 8 |
Correct |
59 ms |
8384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
439 ms |
66132 KB |
Output is correct |
| 2 |
Correct |
423 ms |
66024 KB |
Output is correct |
| 3 |
Correct |
430 ms |
66144 KB |
Output is correct |
| 4 |
Correct |
432 ms |
66120 KB |
Output is correct |
| 5 |
Correct |
430 ms |
66156 KB |
Output is correct |
| 6 |
Correct |
429 ms |
66232 KB |
Output is correct |
| 7 |
Correct |
419 ms |
66152 KB |
Output is correct |
| 8 |
Correct |
407 ms |
66168 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
69 ms |
7908 KB |
Output is correct |
| 12 |
Correct |
88 ms |
9000 KB |
Output is correct |
| 13 |
Correct |
64 ms |
8880 KB |
Output is correct |
| 14 |
Correct |
76 ms |
9020 KB |
Output is correct |
| 15 |
Correct |
70 ms |
8976 KB |
Output is correct |
| 16 |
Correct |
70 ms |
9016 KB |
Output is correct |
| 17 |
Correct |
70 ms |
8544 KB |
Output is correct |
| 18 |
Correct |
59 ms |
8384 KB |
Output is correct |
| 19 |
Correct |
498 ms |
71140 KB |
Output is correct |
| 20 |
Correct |
482 ms |
71232 KB |
Output is correct |
| 21 |
Correct |
500 ms |
71280 KB |
Output is correct |
| 22 |
Correct |
473 ms |
71092 KB |
Output is correct |
| 23 |
Correct |
503 ms |
71208 KB |
Output is correct |
| 24 |
Correct |
505 ms |
71252 KB |
Output is correct |
