| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1269020 | cokalhado | Park (BOI16_park) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mt make_tuple
#define is(x) c.count(x)
const int maxn = 2e3+10;
int n, m;
int w, h;
tuple<int, int, int> tr[maxn];
set<int> ans[maxn];
// 0 means it's a guy, 1 means it's a tree
vector<tuple<int, bool, int, int>> ar;
set<int> edges[maxn]; // edges connected to this guy
int pai[maxn];
int peso[maxn];
int find(int x)
{
if(pai[x] == x) return x;
return pai[x] = find(pai[x]);
}
void join(int a, int b)
{
a = find(a);
b = find(b);
if(a == b) return;
if(peso[a] < peso[b]) swap(a, b);
pai[b] = a;
peso[a] += peso[b];
for(int i : edges[b]) edges[a].insert(i);
}
set<int> cur[5];
void rer(set<int> a)
{
set<int> b;
for(int i = 1; i <= 4; i++)
{
if(!a.count(i)) b.insert(i);
else
{
// cout << "isosing " << i << " ";
}
}
// cout << endl;
for(int i : a)
{
for(int j : b)
{
cur[i].erase(j);
cur[j].erase(i);
}
}
}
int main()
{
cin >> n >> m >> w >> h;
for(int i = 5; i <= n+4; i++)
{
int x, y, r;
cin >> x >> y >> r;
tr[i] = mt(x, y, r);
}
for(int i = 1; i <= m; i++)
{
int r, e;
cin >> r >> e;
ar.push_back(mt(2*r, 0, e, i)); // put the diameter to see if it'll pass
}
for(int i = 1; i <= 4; i++){pai[i] = i; peso[i] = 1; edges[i].insert(i);}
for(int i = 5; i <= n+4; i++)
{
pai[i] = i;
peso[i] = 1;
auto [x, y, r] = tr[i];
vector<pair<int, int>> wall = {{0, y}, {x, h}, {w, y}, {x, 0}};
int c = 0;
for(auto [j, h] : wall)
{
int d = abs(j-x+h-y);
ar.push_back(mt(d-r, 1, i, ++c));
}
for(int j = i+1; j <= n+4; j++)
{
auto [x1, y1, r1] = tr[j];
int dx = x-x1;
int dy = y-y1;
dx *= dx; dy *= dy;
int dist = dx+dy;
// send the distance in which it+1 BREAKS -> (it+1)² > dist
dist = sqrt(dist);
ar.push_back(mt(dist-r-r1, 1, i, j));
}
}
sort(ar.begin(), ar.end());
for(int i = 1; i < 5; i++) cur[i] = {1, 2, 3, 4}; // 1: bl, 2: br, 3: tr, 4: tl
for(auto [size, id, i, j] : ar)
{
if(!id)
{
// put your answer according to the cur
for(int k : cur[i])
{
ans[j].insert(k);
}
}
else
{
join(i, j);
i = pai[i];
set<int> c = edges[i];
set<int> a;
a.clear();
if(is(1) && is(3))
{
a.insert(4); a.insert(3);
rer(a); a.clear();
}
if(is(1) && is(2))
{
a.insert(4);
rer(a); a.clear();
}
if(is(1) && is(4))
{
a.insert(1);
rer(a); a.clear();
}
if(is(2) && is(3))
{
a.insert(3);
rer(a); a.clear();
}
if(is(2) && is(4))
{
a.insert(1); a.insert(4);
rer(a); a.clear();
}
if(is(3) && is(4))
{
a.insert(2);
rer(a); a.clear();
}
}
}
for(int i = 1; i <= m; i++)
{
for(int j : ans[i]) cout << j;
cout << endl;
}
return 0;
}
// 1: bl, 2: br, 3: tr, 4: tl
// 1: left, 2: up, 3: right, 4: down
// 1, 3 -> 4, 3 .remove(1, 2) 1, 2 .remove(3, 4)
// 1, 2 -> 4 .remove(1, 2, 3) 1, 2, 3 .remove(4)
// 1, 4 -> 1 .remove(2, 3, 4) 2, 3, 4 .remove(1)
// 2, 3 -> 3 .remove(1, 2, 4) 1, 2, 4 .remove(3)
// 2, 4 -> 1, 4 .remove(2, 3) 2, 3 .remove(1, 4)
// 3, 4 -> 2 .remove(1, 3, 4) 1, 3, 4 .remove(2)
// 5 3
// 16 11
// 11 8 1
// 6 10 1
// 7 3 2
// 10 4 1
// 15 5 1
// 1 1
// 2 2
// 2 1