| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 754226 |
2023-06-07T09:24:00 Z |
nonono |
Park (BOI16_park) |
C++17 |
|
320 ms |
49688 KB |
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int mxN = 2e3 + 5;
const int mxM = 1e5 + 10;
bool mark[1 << 5], 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[(1 << x) + (1 << y)];
}
int sqr(int x){
return x * x;
}
int sqrDist(int x, int y, int r, int u, int v, int R){
return sqr(abs(x - u) - r - R) + sqr(abs(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] <= sqr(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 = (1 << 5) - 1; mask >= 0; mask --){
if(!mark[mask]) continue ;
for(int _j = 0; _j < 5; _j ++){
if(mask >> _j & 1){
mark[mask ^ (1 << _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] <= sqr(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 |
Incorrect |
320 ms |
49688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
4548 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
320 ms |
49688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
