| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097817 |
2024-10-08T09:50:59 Z |
HuyAT |
Park (BOI16_park) |
C++17 |
|
203 ms |
51900 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i, a) for (int i=0; i<(a); i++)
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
//const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
struct DSU{
vi par, sz;
int n;
DSU(int _n){
n = _n;
sz.assign(n + 1, 1);
par.assign(n + 1, 0);
iota(all(par), 0);
}
int root(int u){
if(par[u] == u) return u;
return par[u] = root(par[u]);
}
bool same(int u, int v){
return root(u) == root(v);
}
void unite(int u, int v){
u = root(u), v = root(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
}
};
const int N = 2010;
const int NN = 1e5 + 5;
struct circle{
int x, y, r;
int dist(circle a){
ld ans = (a.x - x) * (a.x - x) + (a.y - y) * (a.y - y);
return sqrtl(ans);
}
} c[N];
bool ans[NN][5];
struct bruh{
int w, u, v;
bool operator < (bruh &a) const {
return w < a.w;
}
};
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
int w, h; cin >> w >> h;
for(int i = 1; i <= n; ++i) cin >> c[i].x >> c[i].y >> c[i].r;
vector<bruh> query(m);
int rmax = 0;
FOR(i, m){
int e, r; cin >> r >> e;
r *= 2;
rmax = max(rmax, r);
query[i] = {r, e, i};
}
vector<bruh> v;
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
int d = c[i].dist(c[j]);
v.push_back({d - c[i].r - c[j].r, i, j});
}
}
int sz = n;
int n1 = sz + 1, n2 = sz + 2, n3 = sz + 3, n4 = sz + 4;
sz += 4;
int lx = rmax, rx = w - rmax, ly = rmax, ry = h - rmax;
for(int i = 1; i <= n; ++i){
int x = c[i].x, y = c[i].y; ld r = c[i].r;
if(x - r >= lx && x + r <= rx){
v.push_back({y - r, i, n1});
v.push_back({h - y - r, i, n3});
}
if(y - r >= ly && y + r <= ry){
v.push_back({x - r, i, n4});
v.push_back({w - x - r, i, n2});
}
}
sort(all(query));
sort(all(v));
int j = 0, lim = v.size();
DSU dsu(sz);
for(auto &it : query){
int r = it.w, e = it.u, id = it.v;
while(j < lim && v[j].w < r){
int U = v[j].u, V = v[j].v;
dsu.unite(U, V);
++j;
}
for(int i = 1; i <= 4; ++i){
if(i == e)
continue;
if(e == 1){
if(dsu.same(n1, n4)) ans[id][i] = 1;
if(i == 2) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n1, n2));
if(i == 3) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n2, n3));
if(i == 4) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n3, n4));
}
if(e == 2){
if(dsu.same(n1, n2)) ans[id][i] = 1;
if(i == 3) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n2, n3));
if(i == 4) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n3, n4));
if(i == 1) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n1, n4));
}
if(e == 3){
if(dsu.same(n2, n3)) ans[id][i] = 1;
if(i == 4) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n3, n4));
if(i == 1) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n1, n4));
if(i == 2) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n1, n2));
}
if(e == 4){
if(dsu.same(n3, n4)) ans[id][i] = 1;
if(i == 1) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n1, n4));
if(i == 2) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n1, n2));
if(i == 3) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n3));
}
}
}
FOR(i, m){
for(int j = 1; j <= 4; ++j) if(!ans[i][j]) cout << j;
cout << "\n";
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:90:28: warning: narrowing conversion of '((ld)y - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
90 | v.push_back({y - r, i, n1});
| ~~^~~
park.cpp:91:32: warning: narrowing conversion of '((ld)(h - y) - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
91 | v.push_back({h - y - r, i, n3});
| ~~~~~~^~~
park.cpp:94:28: warning: narrowing conversion of '((ld)x - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
94 | v.push_back({x - r, i, n4});
| ~~^~~
park.cpp:95:32: warning: narrowing conversion of '((ld)(w - x) - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
95 | v.push_back({w - x - r, i, n2});
| ~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
50424 KB |
Output is correct |
| 2 |
Correct |
203 ms |
51304 KB |
Output is correct |
| 3 |
Correct |
197 ms |
50300 KB |
Output is correct |
| 4 |
Correct |
200 ms |
51388 KB |
Output is correct |
| 5 |
Correct |
203 ms |
51900 KB |
Output is correct |
| 6 |
Correct |
201 ms |
51324 KB |
Output is correct |
| 7 |
Correct |
189 ms |
51124 KB |
Output is correct |
| 8 |
Correct |
177 ms |
50100 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
4052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
193 ms |
50424 KB |
Output is correct |
| 2 |
Correct |
203 ms |
51304 KB |
Output is correct |
| 3 |
Correct |
197 ms |
50300 KB |
Output is correct |
| 4 |
Correct |
200 ms |
51388 KB |
Output is correct |
| 5 |
Correct |
203 ms |
51900 KB |
Output is correct |
| 6 |
Correct |
201 ms |
51324 KB |
Output is correct |
| 7 |
Correct |
189 ms |
51124 KB |
Output is correct |
| 8 |
Correct |
177 ms |
50100 KB |
Output is correct |
| 9 |
Correct |
0 ms |
348 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Incorrect |
39 ms |
4052 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
