| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 350906 | Hossein29 | Park (BOI16_park) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e3+10;
const int maxm = 2e2+10;
const int inf = 1e9+1;
int n,m,w,h;
int tree[maxn][3]; // x , y , r
int vis[maxm][2]; // e , r
int p[maxn],sz[maxn],l[maxn],r[maxn],t[maxn],b[maxn],block[4][4];
vector<int>G[maxm];
int get_parent(int v){
if(p[v] == v)
return v;
return p[v] = get_parent(p[v]);
}
void make_union(int v,int u, int r1){
int a1 = get_parent(v);
int b1 = get_parent(u);
if(a1 == b1) return;
if((min(abs(r[a1] - l[b1]),abs(r[b1] - l[a1]))) < 2*r1){
if(min(abs(t[b1] - b[a1]),abs(b[b1] - t[a1])) < 2*r1){
if(sz[a1] < sz[b1])
swap(a1,b1);
p[b1] = a1;
sz[a1] += sz[b1];
l[a1] = min(l[a1],l[b1]);
r[a1] = max(r[a1],r[b1]);
t[a1] = max(t[a1],t[b1]);
b[a1] = min(b[a1],b[b1]);
}
}
if(l[a1] == 0 && t[a1] == h) block[1][2] = true;
if(l[a1] == 0 && r[a1] == w) block[1][3] = true;
if(l[a1] == 0 && b[a1] == 0) block[1][4] = true;
if(t[a1] == h && r[a1] == w) block[2][3] = true;
if(t[a1] == h && b[a1] == 0) block[2][4] = true;
if(r[a1] == w && b[a1] == 0) block[3][4] = true;
}
int32_t main(){
ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
////////////////////////////////////////////////
cin >> n >> m >> w >> h;
for(int i = 1;i<=n;i++){
cin >> tree[i][0] >> tree[i][1] >> tree[i][2];
}
for(int i = 0;i<m;i++){
cin >> vis[i][0] >> vis[i][1];
for(int j = 1;j<=n;j++){
p[j] = j;
sz[j] = 1;
l[j] = max(0,(tree[j][0]-tree[j][2] < 2*vis[i][1] ? 0 : tree[j][0]-tree[j][2]));
r[j] = min(w,(tree[j][0]+tree[j][2] + 2*vis[i][1] <= w ? tree[j][0]+tree[j][2] : w));
t[j] = min(h,(tree[j][1]+tree[j][2] + 2*vis[i][1] <= h ? tree[j][0]+tree[j][2] : h));
b[j] = max(0,(tree[j][1]-tree[j][2] - 2*vis[i][1] < 0 ? 0 : tree[j][1]-tree[j][2]));
int a = j;
if(l[a] == 0 && t[a] == h) block[1][2] = true;
if(l[a] == 0 && r[a] == w) block[1][3] = true;
if(l[a] == 0 && b[a] == 0) block[1][4] = true;
if(t[a] == h && r[a] == w) block[2][3] = true;
if(t[a] == h && b[a] == 0) block[2][4] = true;
if(r[a] == w && b[a] == 0) block[3][4] = true;
}
for(int j = 0;j<6;j++){
for(int k = 0;k<6;k++){
block[i][j] = false;
}
}
for(int j = 2;j<=n;j++){
make_union(j,j-1,vis[i][0]);
}
if(vis[i][0] == 1){
G[i].push_back(1);
if(block[1][4] == true) continue;
if(block[1][3] == false && block[1][2] == false) G[i].push_back(4);
if(block[2][4] == false && block[3][4] == false) G[i].push_back(2);
if(block[1][3] == false && block[2][4] == false && block[2][3] == false) G[i].push_back(3);
}
else if(vis[i][1] == 2){
G[i].push_back(2);
if(block[3][4] == true) continue;
if(block[1][4] == false && block[2][4] == false) G[i].push_back(1);
if(block[2][3] == false && block[1][3] == false) G[i].push_back(3);
if(block[1][3] == false && block[2][4] == false && block[1][2] == false) G[i].push_back(4);
}
else if(vis[i][2] == 3){
G[i].push_back(3);
if(block[2][3] == true) continue;
if(block[3][4] == false && block[1][3] == false) G[i].push_back(2);
if(block[2][4] == false && block[1][2] == false) G[i].push_back(4);
if(block[1][4] == false && block[2][4] == false && block[1][3] == false) G[i].push_back(1);
}
else{
G[i].push_back(4);
if(block[1][2] == true) continue;
if(block[1][4] == false && block[1][3] == false) G[i].push_back(1);
if(block[1][3] == false && block[2][4] == false && block[3][4] == false) G[i].push_back(2);
if(block[2][3] == false && block[2][4] == false) G[i].push_back(3);
}
}
for(int i = 0;i<m;i++){
sort(G[i].begin(),G[i].end());
for(int b : G[i])
cout << b;
cout << "\n";
}
return 0;
}