| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 525169 |
2022-02-11T01:55:38 Z |
vijay |
Park (BOI16_park) |
C++17 |
|
521 ms |
70236 KB |
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <array>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
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>
const ll M = 1000000007;
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);
// ifstream cin;
// cin.open("test.in");
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:153: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]
153 | 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:123:29: required from here
park.cpp:44:42: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
44 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
| ^
park.cpp:45:19: note: in expansion of macro 'FOR'
45 | #define F0R(i, a) FOR(i,0,a)
| ^~~
park.cpp:51:5: note: in expansion of macro 'F0R'
51 | F0R(i, N) in >> arr[i];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
419 ms |
66024 KB |
Output is correct |
| 2 |
Correct |
423 ms |
66092 KB |
Output is correct |
| 3 |
Correct |
424 ms |
66112 KB |
Output is correct |
| 4 |
Correct |
417 ms |
66040 KB |
Output is correct |
| 5 |
Correct |
439 ms |
66092 KB |
Output is correct |
| 6 |
Correct |
461 ms |
66240 KB |
Output is correct |
| 7 |
Correct |
416 ms |
66024 KB |
Output is correct |
| 8 |
Correct |
405 ms |
66136 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 |
77 ms |
7900 KB |
Output is correct |
| 2 |
Correct |
68 ms |
7904 KB |
Output is correct |
| 3 |
Correct |
67 ms |
7896 KB |
Output is correct |
| 4 |
Correct |
66 ms |
7880 KB |
Output is correct |
| 5 |
Correct |
69 ms |
7868 KB |
Output is correct |
| 6 |
Correct |
93 ms |
7912 KB |
Output is correct |
| 7 |
Correct |
64 ms |
7164 KB |
Output is correct |
| 8 |
Correct |
60 ms |
7176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
419 ms |
66024 KB |
Output is correct |
| 2 |
Correct |
423 ms |
66092 KB |
Output is correct |
| 3 |
Correct |
424 ms |
66112 KB |
Output is correct |
| 4 |
Correct |
417 ms |
66040 KB |
Output is correct |
| 5 |
Correct |
439 ms |
66092 KB |
Output is correct |
| 6 |
Correct |
461 ms |
66240 KB |
Output is correct |
| 7 |
Correct |
416 ms |
66024 KB |
Output is correct |
| 8 |
Correct |
405 ms |
66136 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
77 ms |
7900 KB |
Output is correct |
| 12 |
Correct |
68 ms |
7904 KB |
Output is correct |
| 13 |
Correct |
67 ms |
7896 KB |
Output is correct |
| 14 |
Correct |
66 ms |
7880 KB |
Output is correct |
| 15 |
Correct |
69 ms |
7868 KB |
Output is correct |
| 16 |
Correct |
93 ms |
7912 KB |
Output is correct |
| 17 |
Correct |
64 ms |
7164 KB |
Output is correct |
| 18 |
Correct |
60 ms |
7176 KB |
Output is correct |
| 19 |
Correct |
506 ms |
70184 KB |
Output is correct |
| 20 |
Correct |
480 ms |
70128 KB |
Output is correct |
| 21 |
Correct |
504 ms |
70236 KB |
Output is correct |
| 22 |
Correct |
521 ms |
70112 KB |
Output is correct |
| 23 |
Correct |
489 ms |
70116 KB |
Output is correct |
| 24 |
Correct |
472 ms |
70220 KB |
Output is correct |
