| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1301656 | notbraining | Park (BOI16_park) | C++20 | 0 ms | 0 KiB |
//#pragma GCC optimize ("O3")
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#include <cassert>
#include<algorithm>
#include <cstring>
#include<unordered_set>
#include<queue>
#include <array>
#include<cmath>
#include<unordered_map>
#include<queue>
#include <list>
#include <bitset>
using namespace std;
#define int long long
#define pii pair<int,int>
#define LL long long
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt”)
int INF = 1e18;
int n, m, w, h;
vector<pii>events;
vector<vector<int>>ans;
vector<pair<pii, int>>trees;
int relation[5][5];
int firstworks[5][5];
struct DSU{
vector<int> par;
vector<int>sz;
DSU(int _n){
par = vector<int>(_n + 1);
sz = vector<int>(_n + 1, 1);
for(int i = 0; i <= _n; ++i){
par[i] = i;
}
}
//with path compression
int get(int x) { return (par[x] == x ? x : (par[x] = get(par[x]))); }
//small to large merging
void uni(int a, int b) {
a = get(a);
b = get(b);
if(a == b) return;
if(sz[a] > sz[b]) {
swap(a, b);
}
sz[b] += sz[a];
par[a] = b;
}
bool sameset(int a, int b){
return get(a) == get(b);
}
};
int distsq(pii a, pii b){
return (b.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second);
}
bool canpass(int rad, int t1, int t2){
int dsq = distsq(trees[t1].first, trees[t2].first);
if(rad == 2 && t1 == 3 + 3 && t2 == 5 + 3){
//cout << "AYYO";
//cout << dsq << endl;
//cout << (2 * rad + trees[t1].second + trees[t2].second) * (2 * rad + trees[t1].second + trees[t2].second) << endl;
}
if((2 * rad + trees[t1].second + trees[t2].second) * (2 * rad + trees[t1].second + trees[t2].second) <= dsq){
return true;
}
return false;
}
bool check(int rad, int ent, int ex){ //horz = 0, vertical = 1
DSU dsu(n + 10);
for(int i = 4; i < n + 4; ++i){
auto [x, y] = trees[i].first;
for(int j = 0; j < n + 4; ++j){
if(i == j)
continue;
if(j >= 4){
if(!canpass(rad, i, j)){
dsu.uni(i, j);
//cout << i - 3 << " " << j - 3 << endl;
}
} else{
int space = 0;
if(j == 0){
space = h - y;
}
if(j == 1){
space = x;
}
if(j == 2){
space = y;
}
if(j == 3){
space = h - x;
}
if(space < 2 * rad)
dsu.uni(i, j);
}
}
}
if(ent == 1){
if(dsu.sameset(1, 2))
return false;
}
if(ent == 2){
if(dsu.sameset(2, 3))
return false;
}
if(ent == 3){
if(dsu.sameset(0, 3))
return false;
}
if(ent == 4){
if(dsu.sameset(1, 0))
return false;
}
int r = relation[ent][ex];
if(r == 0){
// vertical movement
if(dsu.sameset(1, 3))
return false;
}
if(r == 1){
//horizontal moment
if(dsu.sameset(0, 2))
return false;
}
if(r == 2){
if(ent == 3 || ex == 3){
if(dsu.sameset(1, 2) || dsu.sameset(0, 3))
return false;
}
if(ent == 4 || ex == 4){
if(dsu.sameset(1, 0) || dsu.sameset(2, 3))
return false;
}
}
// cout << "YO we made it: " << rad << " " << ent << " " << ex << endl;
return true;
}
void solve(int ent){
for(int ex = ent + 1; ex <= 4; ++ex){
int l = 1;
int r = 1e9;
while(l <= r){
int mid = (l + r) / 2;
if(check(mid, ent, ex)){
//ok
l = mid + 1;
} else{
r = mid - 1;
}
}
int okbound = r;
firstworks[ent][ex] = okbound;
firstworks[ex][ent] = okbound;
// cout << "ex and ent: " << ex << " " << ent << " okbound: " << okbound << endl;
}
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> w >> h;
events = vector<pii>(m);
ans = vector<vector<int>>(n + 1);
trees = vector<pair<pii, int>>(4);//4 parts already
relation[1][4] = 0;
relation[1][2] = 1;
relation[1][3] = 2;
relation[2][3] = 0;
relation[2][4] = 2;
relation[3][4] = 1;
for(int i = 0; i < n; ++i){
int x, y, r;
cin >> x >> y >> r;
trees.push_back({{x, y}, r});
}
for(int i = 0; i < m; ++i){
int r, e; cin >> r >> e;
events[i] = {r, e};
}
//solve(2);
//return 0;
for(int i = 1; i <= 4; ++i){
solve(i);
}
for(int i = 0; i < m; ++i){
auto [r, e] = events[i];
ans[i].push_back(e);
for(int j = 1; j <= 4; ++j){
if(j == e)
continue;
if(r <= firstworks[j][e]){
//it is ok!
ans[i].push_back(j);
}
}
}
for(int i = 0; i < m; ++i){
for(int j : ans[i])
cout << j << " ";
cout << "\n";
}
}