#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
const long double eps = 1e-9;
struct DSU{
int n;
vector<int> pa, sz;
DSU(int n) : n(n){
pa.resize(n+1);
sz.resize(n+1, 1);
for(int i = 0; i <= n; i++){
pa[i] = i;
}
};
int find(int x){
while(x != pa[x]){
x = pa[x] = pa[pa[x]];
}
return x;
}
bool same(int x, int y){
return find(x) == find(y);
}
bool merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(sz[x] < sz[y]) swap(x, y);
pa[y] = x;
sz[x] += sz[y];
return true;
}
int size(int x){
return sz[find(x)];
}
};
struct plant{
ll x, y, r;
};
struct man{
ll t, r, id;
};
struct edge{
int u, v;
long double w;
};
void solve(){
int n, m;
cin >> n >> m;
ll w, h;
cin >> w >> h;
vector<plant> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i].x >> a[i].y >> a[i].r;
}
vector<man> b(m+1);
for(int i = 1; i <= m; i++){
cin >> b[i].r >> b[i].t;
b[i].id = i;
}
auto d = [&](int i, int j) -> long double{
return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
};
vector<edge> pr;
for(int i = 1; i <= n; i++){
for(int j = 1; j < i; j++){
pr.push_back({i, j, d(i, j)-a[i].r-a[j].r});
}
pr.push_back({i, n+1, a[i].y-a[i].r});
pr.push_back({i, n+2, w-a[i].x-a[i].r});
pr.push_back({i, n+3, h-a[i].y-a[i].r});
pr.push_back({i, n+4, a[i].x-a[i].r});
}
sort(b.begin()+1, b.end(), [&](man a, man b){return a.r < b.r;});
sort(pr.begin(), pr.end(), [&](edge a, edge b){return a.w < b.w;});
int j = 0;
auto cmp = [&](long double a, long double b) -> bool{
return b-a > eps;
};
int N = pr.size()+10;
DSU dsu(N);
vector<int> s;
vector<vector<int>> ans(m+1);
for(int i = 1; i <= m; i++){
while(j < pr.size() && cmp(pr[j].w, b[i].r*2)){
dsu.merge(pr[j].u, pr[j].v);
j++;
}
int id = b[i].id;
s.clear();
if(b[i].t == 1){
s.push_back(1);
if(dsu.same(n+1, n+2) || dsu.same(n+1, n+3) || dsu.same(n+1, n+4)){
}else{
s.push_back(2);
}
if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4) || dsu.same(n+1, n+4)){
}else{
s.push_back(3);
}
if(dsu.same(n+1, n+4) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4)){
}else{
s.push_back(4);
}
}
if(b[i].t == 2){
s.push_back(2);
if(dsu.same(n+1, n+2) || dsu.same(n+1, n+3) || dsu.same(n+1, n+4)){
}else{
s.push_back(1);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){
}else{
s.push_back(3);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4) || dsu.same(n+1, n+3)){
}else{
s.push_back(4);
}
}
if(b[i].t == 3){
s.push_back(3);
if(dsu.same(n+1, n+3) || dsu.same(n+1, n+4) || dsu.same(n+2, n+3), dsu.same(n+2, n+4)){
}else{
s.push_back(1);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){
}else{
s.push_back(2);
}
if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+3, n+4)){
}else{
s.push_back(4);
}
}
if(b[i].t == 4){
s.push_back(4);
if(dsu.same(n+1, n+4) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4)){
}else{
s.push_back(1);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4) || dsu.same(n+1, n+3)){
}else{
s.push_back(2);
}
if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){
}else{
s.push_back(3);
}
}
sort(s.begin(), s.end());
ans[id] = s;
}
for(int i = 1; i <= m; i++){
for(int j : ans[i]){
cout << j;
}
cout << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Compilation message
park.cpp: In function 'void solve()':
park.cpp:71:37: warning: narrowing conversion of '(a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::y - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
71 | pr.push_back({i, n+1, a[i].y-a[i].r});
park.cpp:72:39: warning: narrowing conversion of '((w - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::x) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
72 | pr.push_back({i, n+2, w-a[i].x-a[i].r});
| ~~~~~~~~^~~~~~~
park.cpp:73:39: warning: narrowing conversion of '((h - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::y) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
73 | pr.push_back({i, n+3, h-a[i].y-a[i].r});
| ~~~~~~~~^~~~~~~
park.cpp:74:37: warning: narrowing conversion of '(a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::x - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
74 | pr.push_back({i, n+4, a[i].x-a[i].r});
park.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while(j < pr.size() && cmp(pr[j].w, b[i].r*2)){
| ~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
386 ms |
79252 KB |
Output is correct |
| 2 |
Correct |
371 ms |
80792 KB |
Output is correct |
| 3 |
Correct |
368 ms |
79516 KB |
Output is correct |
| 4 |
Correct |
365 ms |
79328 KB |
Output is correct |
| 5 |
Correct |
389 ms |
80788 KB |
Output is correct |
| 6 |
Incorrect |
380 ms |
80668 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
41 ms |
9424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
386 ms |
79252 KB |
Output is correct |
| 2 |
Correct |
371 ms |
80792 KB |
Output is correct |
| 3 |
Correct |
368 ms |
79516 KB |
Output is correct |
| 4 |
Correct |
365 ms |
79328 KB |
Output is correct |
| 5 |
Correct |
389 ms |
80788 KB |
Output is correct |
| 6 |
Incorrect |
380 ms |
80668 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
