// PhuThuyRuntime <3
// A secret makes a woman woman
#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << "\n";
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define ull unsigned long long
#define pob pop_back
#define bs binary_search
#define vi vector<int>
#define vii vector<pair<int, int>>
#define getbit(i, j) ((i >> j) & 1)
#define offbit(i, j) ((1 << j) ^ i)
#define onbit(i, j) ((1 << j) | i)
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
const int inf = INT_MAX;
const int base = 31;
const long double EPS = 1e-9;
const long double pi = acos(-1.0);
int n, m, w, h;
struct person{
ll fi, se, val;
bool operator < (const person &other) const{
return fi < other.fi;
}
} a[2002];
struct tree{
ll fi, se, val;
bool operator < (const tree &other) const{
return val < other.val;
}
} b[N];
void inp(){
cin >> n >> m >> w >> h;
fo(i, 1, n) cin >> a[i].fi >> a[i].se >> a[i].val;
fo(i, 1, m){
cin >> b[i].fi >> b[i].se;
b[i].val = i;
}
}
struct dsu{
int par[2 * N], sz[2 * N];
void makeset(int u){
par[u] = u;
sz[u] = 1;
}
int findset(int u){
return u == par[u] ? u : par[u] = findset(par[u]);
}
void joinset(int u, int v){
u = findset(u);
v = findset(v);
if(u == v) return;
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
} dsu;
long long distance(int u, int v){
return (ll)sqrt((a[u].fi - a[v].fi) * (a[u].fi - a[v].fi) + (a[u].se - a[v].se) * (a[u].se - a[v].se)) + 1;
}
vector<tree> edges;
string ans[N];
void sol(){
sort(b + 1, b + m + 1);
fo(i, 1, n){
edges.push_back({i, n + 1, a[i].fi - a[i].val + 1});
edges.push_back({i, n + 2, h - (a[i].se + a[i].val) + 1});
edges.push_back({i, n + 3, w - (a[i].fi + a[i].val) + 1});
edges.push_back({i, n + 4, a[i].se - a[i].val + 1});
fo(j, i + 1, n){
edges.push_back({i, j, distance(i, j) - a[i].val - a[j].val});
}
}
fo(i, 1, n + 4) dsu.makeset(i);
sort(all(edges));
int j = 0;
fo(i, 1, m){
while(j < (int)edges.size() && edges[j].val <= b[i].fi * 2){
dsu.joinset(edges[j].fi, edges[j].se);
j++;
}
int start = b[i].se, id = b[i].val;
ans[id] += char(start + '0');
if (start == 1){
if (dsu.findset(n + 4) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 4))
ans[id] += '2';
if (dsu.findset(n + 2) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 4))
ans[id] += '3';
if (dsu.findset(n + 1) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 4))
ans[id] += '4';
}
else if (start == 2){
if (dsu.findset(n + 1) != dsu.findset(n + 4) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 4) != dsu.findset(n + 3))
ans[id] += '1';
if (dsu.findset(n + 2) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 3))
ans[id] += '3';
if (dsu.findset(n + 1) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 2) != dsu.findset(n + 4) && dsu.findset(n + 4) != dsu.findset(n + 3))
ans[id] += '4';
}
else if (start == 3){
if (dsu.findset(n + 1) != dsu.findset(n + 4) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 2) != dsu.findset(n + 3))
ans[id] += '1';
if (dsu.findset(n + 3) != dsu.findset(n + 4) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 2) != dsu.findset(n + 3))
ans[id] += '2';
if (dsu.findset(n + 1) != dsu.findset(n + 2) && dsu.findset(n + 2) != dsu.findset(n + 4) && dsu.findset(n + 2) != dsu.findset(n + 3))
ans[id] += '4';
}
else if (start == 4){
if (dsu.findset(n + 4) != dsu.findset(n + 1) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 2))
ans[id] += '1';
if (dsu.findset(n + 4) != dsu.findset(n + 3) && dsu.findset(n + 4) != dsu.findset(n + 2) && dsu.findset(n + 1) != dsu.findset(n + 3) && dsu.findset(n + 1) != dsu.findset(n + 2))
ans[id] += '2';
if (dsu.findset(n + 3) != dsu.findset(n + 2) && dsu.findset(n + 2) != dsu.findset(n + 4) && dsu.findset(n + 1) != dsu.findset(n + 2))
ans[id] += '3';
}
}
fo(i, 1, m){
sort(all(ans[i]));
cout << ans[i], el
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
inp();
sol();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
182 ms |
58292 KB |
Output is correct |
| 2 |
Correct |
178 ms |
58292 KB |
Output is correct |
| 3 |
Correct |
179 ms |
58292 KB |
Output is correct |
| 4 |
Correct |
186 ms |
58284 KB |
Output is correct |
| 5 |
Correct |
184 ms |
58292 KB |
Output is correct |
| 6 |
Correct |
198 ms |
58276 KB |
Output is correct |
| 7 |
Correct |
183 ms |
58292 KB |
Output is correct |
| 8 |
Correct |
173 ms |
58292 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6904 KB |
Output is correct |
| 10 |
Correct |
2 ms |
6736 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
25 ms |
9360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
182 ms |
58292 KB |
Output is correct |
| 2 |
Correct |
178 ms |
58292 KB |
Output is correct |
| 3 |
Correct |
179 ms |
58292 KB |
Output is correct |
| 4 |
Correct |
186 ms |
58284 KB |
Output is correct |
| 5 |
Correct |
184 ms |
58292 KB |
Output is correct |
| 6 |
Correct |
198 ms |
58276 KB |
Output is correct |
| 7 |
Correct |
183 ms |
58292 KB |
Output is correct |
| 8 |
Correct |
173 ms |
58292 KB |
Output is correct |
| 9 |
Correct |
1 ms |
6904 KB |
Output is correct |
| 10 |
Correct |
2 ms |
6736 KB |
Output is correct |
| 11 |
Incorrect |
25 ms |
9360 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
