| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 754240 |
2023-06-07T10:08:47 Z |
nonono |
Park (BOI16_park) |
C++14 |
|
383 ms |
53216 KB |
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int mxN = 2e3 + 5;
const int mxM = 1e5 + 10;
bool mark[1LL << 5LL], check[mxM][5];
struct DSU {
vector<int> lab, dir;
void init(int n){
lab.resize(n + 5);
dir.resize(n + 5);
for(int i = 1; i <= n; i ++){
lab[i] = -1;
dir[i] = 0;
}
}
int get_root(int u){
return lab[u] < 0 ? u : lab[u] = get_root(lab[u]);
}
bool unite(int u, int v){
u = get_root(u);
v = get_root(v);
if(u == v) return false;
if(lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
dir[u] |= dir[v];
mark[dir[u]] = true;
lab[v] = u;
return true;
}
} dsu;
int n, m, w, h;
array<int, 3> a[mxN], b[mxM];
bool f(int x, int y){
return mark[(1LL << x) + (1LL << y)];
}
int sqr(int x){
return x * x;
}
int sqrDist(int x, int y, int r, int u, int v, int R){
return sqrtl(sqr(x - u) + sqr(y - v)) - r - R;
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> w >> h;
dsu.init(n);
memset(mark, false, sizeof(mark));
for(int i = 1; i <= n; i ++){
int x, y, R;
cin >> x >> y >> R;
a[i] = {x, y, R};
}
for(int i = 1; i <= m; i ++){
int R, e;
cin >> R >> e;
b[i] = {R, e, i};
}
sort(b + 1, b + 1 + m);
vector<array<int, 3>> edge;
for(int i = 1; i <= n; i ++){
int x = a[i][0];
int y = a[i][1];
int r = a[i][2];
for(int j = i + 1; j <= n; j ++){
int u = a[j][0];
int v = a[j][1];
int R = a[j][2];
edge.push_back({sqrDist(x, y, r, u, v, R), i, j});
}
}
sort(edge.begin(), edge.end());
vector<array<int, 3>> D;
for(int i = 1; i <= n; i ++){
int x, y;
int R = a[i][2];
x = w - a[i][0] - R;
D.push_back({x, i, 2});
x = a[i][0] - R;
D.push_back({x, i, 8});
y = h - a[i][1] - R;
D.push_back({y, i, 1});
y = a[i][1] - R;
D.push_back({y, i, 4});
}
sort(D.begin(), D.end());
for(int i = 1, j = 0, k = 0; i <= m; i ++){
int R = b[i][0] * 2;
int e = b[i][1];
int id = b[i][2];
while(j < edge.size() && edge[j][0] < R){
int u = edge[j][1];
int v = edge[j][2];
dsu.unite(u, v);
j ++ ;
}
while(k < D.size() && D[k][0] < R){
int u = dsu.get_root(D[k][1]);
dsu.dir[u] |= D[k][2];
mark[dsu.dir[u]] = true;
k ++ ;
}
for(int mask = (1LL << 5LL) - 1; mask >= 0; mask --){
if(!mark[mask]) continue ;
for(int _j = 0; _j < 5; _j ++){
if(mask >> _j & 1LL){
mark[mask ^ (1LL << _j)] = true;
}
}
}
for(int _j = 1; _j <= 4; _j ++) check[id][_j] = true;
if(e == 1){
if(f(2, 3)) check[id][2] = check[id][3] = check[id][4] = false;
if(f(0, 2)) check[id][2] = check[id][3] = false;
if(f(1, 3)) check[id][3] = check[id][4] = false;
if(f(1, 2)) check[id][2] = false;
if(f(0, 1)) check[id][3] = false;
if(f(0, 3)) check[id][4] = false;
}
if(e == 2){
if(f(1, 2)) check[id][1] = check[id][3] = check[id][4] = false;
if(f(0, 2)) check[id][1] = check[id][4] = false;
if(f(1, 3)) check[id][3] = check[id][4] = false;
if(f(2, 3)) check[id][1] = false;
if(f(0, 1)) check[id][3] = false;
if(f(0, 3)) check[id][4] = false;
}
if(e == 3){
if(f(0, 1)) check[id][1] = check[id][2] = check[id][4] = false;
if(f(0, 2)) check[id][1] = check[id][4] = false;
if(f(1, 3)) check[id][1] = check[id][2] = false;
if(f(2, 3)) check[id][1] = false;
if(f(1, 2)) check[id][2] = false;
if(f(0, 3)) check[id][4] = false;
}
if(e == 4){
if(f(0, 3)) check[id][1] = check[id][2] = check[id][3] = false;
if(f(0, 2)) check[id][2] = check[id][3] = false;
if(f(1, 3)) check[id][1] = check[id][2] = false;
if(f(2, 3)) check[id][1] = false;
if(f(1, 2)) check[id][2] = false;
if(f(0, 1)) check[id][3] = false;
}
}
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= 4; j ++){
if(check[i][j]) cout << j;
}
cout << "\n";
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:126:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | while(j < edge.size() && edge[j][0] < R){
| ~~^~~~~~~~~~~~~
park.cpp:134:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | while(k < D.size() && D[k][0] < R){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
49816 KB |
Output is correct |
| 2 |
Correct |
303 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
315 ms |
49804 KB |
Output is correct |
| 4 |
Correct |
301 ms |
49872 KB |
Output is correct |
| 5 |
Correct |
345 ms |
49792 KB |
Output is correct |
| 6 |
Correct |
320 ms |
49816 KB |
Output is correct |
| 7 |
Correct |
314 ms |
49820 KB |
Output is correct |
| 8 |
Correct |
282 ms |
49784 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
5056 KB |
Output is correct |
| 2 |
Correct |
48 ms |
5140 KB |
Output is correct |
| 3 |
Correct |
51 ms |
5060 KB |
Output is correct |
| 4 |
Correct |
52 ms |
5140 KB |
Output is correct |
| 5 |
Correct |
54 ms |
5072 KB |
Output is correct |
| 6 |
Correct |
53 ms |
5116 KB |
Output is correct |
| 7 |
Correct |
48 ms |
4612 KB |
Output is correct |
| 8 |
Correct |
47 ms |
4596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
49816 KB |
Output is correct |
| 2 |
Correct |
303 ms |
49756 KB |
Output is correct |
| 3 |
Correct |
315 ms |
49804 KB |
Output is correct |
| 4 |
Correct |
301 ms |
49872 KB |
Output is correct |
| 5 |
Correct |
345 ms |
49792 KB |
Output is correct |
| 6 |
Correct |
320 ms |
49816 KB |
Output is correct |
| 7 |
Correct |
314 ms |
49820 KB |
Output is correct |
| 8 |
Correct |
282 ms |
49784 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
336 KB |
Output is correct |
| 11 |
Correct |
52 ms |
5056 KB |
Output is correct |
| 12 |
Correct |
48 ms |
5140 KB |
Output is correct |
| 13 |
Correct |
51 ms |
5060 KB |
Output is correct |
| 14 |
Correct |
52 ms |
5140 KB |
Output is correct |
| 15 |
Correct |
54 ms |
5072 KB |
Output is correct |
| 16 |
Correct |
53 ms |
5116 KB |
Output is correct |
| 17 |
Correct |
48 ms |
4612 KB |
Output is correct |
| 18 |
Correct |
47 ms |
4596 KB |
Output is correct |
| 19 |
Correct |
349 ms |
53152 KB |
Output is correct |
| 20 |
Correct |
367 ms |
53116 KB |
Output is correct |
| 21 |
Correct |
335 ms |
53140 KB |
Output is correct |
| 22 |
Correct |
350 ms |
53140 KB |
Output is correct |
| 23 |
Correct |
350 ms |
53116 KB |
Output is correct |
| 24 |
Correct |
383 ms |
53216 KB |
Output is correct |
