| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097773 |
2024-10-08T08:58:21 Z |
HuyAT |
Park (BOI16_park) |
C++14 |
|
412 ms |
94664 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; ld r;
ld 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{
ld w;
int 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;
rmax = max(rmax, r);
query[i] = {r * 2, e, i};
}
vector<bruh> v;
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
ld d = c[i].dist(c[j]);
v.push_back({d - c[i].r - c[j].r, i, j});
}
}
int sz = v.size();
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, r = c[i].r;
if(x - r >= lx && x + r <= rx){
v.push_back({y, i, n1});
v.push_back({h - y, i, n3});
}
if(y - r >= ly && y + r <= ry){
v.push_back({x, i, n4});
v.push_back({w - x, i, n2});
}
}
sort(all(query));
sort(all(v));
int j = 0;
DSU dsu(sz);
for(auto &it : query){
ld r = it.w; int e = it.u, id = it.v;
while(j < sz && 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:74:23: warning: narrowing conversion of '(r * 2)' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
74 | query[i] = {r * 2, e, i};
| ~~^~~
park.cpp:90:26: warning: narrowing conversion of 'y' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
90 | v.push_back({y, i, n1});
| ^
park.cpp:91:28: warning: narrowing conversion of '(h - y)' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
91 | v.push_back({h - y, i, n3});
| ~~^~~
park.cpp:94:26: warning: narrowing conversion of 'x' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
94 | v.push_back({x, i, n4});
| ^
park.cpp:95:28: warning: narrowing conversion of '(w - x)' from 'long long int' to 'ld' {aka 'long double'} [-Wnarrowing]
95 | v.push_back({w - x, i, n2});
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
94608 KB |
Output is correct |
| 2 |
Incorrect |
403 ms |
94664 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
5324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
94608 KB |
Output is correct |
| 2 |
Incorrect |
403 ms |
94664 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
