| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1003509 | sano | 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<iostream>
#include<vector>
#include<queue>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short ll
#define pii pair<ll, ll>
#define NEK 1000000000
#define mod1 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
using namespace std;
vec<int> o;
double dist(pii a, pii b) {
return sqrt(abs(a.ff - b.ff) * abs(a.ff - b.ff) + abs(a.ss - b.ss) * abs(a.ss - b.ss));
}
struct strom {
ll x, y, r;
};
struct hrana {
ll x, y;
double w;
bool operator<(const hrana& other) const {
return w > other.w;
}
};
struct clovek {
ll r, e, ind;
bool operator<(const clovek& other) const {
return r < other.r;
}
};
int otec(int x) {
if (o[x] < 0) return x;
o[x] = otec(o[x]);
return o[x];
}
bool spoj(int a, int b) {
if (otec(a) == otec(b)) return true;
o[otec(b)] = otec(a);
return true;
}
bool je(int a, int b) {
return otec(a) == otec(b);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll n, m, w, h;
cin >> n >> m >> w >> h;
vec<strom> s;
For(i, n) {
ll x, y, r;
cin >> x >> y >> r;
s.push_back({ x, y, r });
}
vec<hrana> p;
For(i, n) {
For(j, n) {
if (i == j) continue;
p.push_back({ i, j, { double((dist({s[i].x, s[i].y}, {s[j].x, s[j].y}) - s[i].r - s[j].r) / 2) } });
}
}
For(i, n) {
p.push_back({ i, n, double((s[i].y - s[i].r) / 2) });
p.push_back({ i, n + 1, double((w - s[i].x - s[i].r) / 2) });
p.push_back({ i, n + 2, double((h - s[i].y - s[i].r) / 2) });
p.push_back({ i, n + 3, double((s[i].x - s[i].r) / 2) });
}
o.resize(n + 4, -1);
sort(p.begin(), p.end());
vec<clovek> l;
vec<vec<bool>> odp(m, vec<bool>(4, false));
For(i, m) {
ll r, e;
cin >> r >> e;
l.push_back({ r, e, i });;
}
sort(l.begin(), l.end());
For(i, m) {
ll r = l[i].r; ll e = l[i].e;
while (!p.empty()) {
if (p.back().w >= r) break;
spoj(p.back().x, p.back().y);
p.pop_back();
}
int v1 = e - 1;
int v2 = e;
int v3 = e + 1;
int v4 = e + 2;
if (v2 > 3) v2 -= 4;
if (v3 > 3) v3 -= 4;
if (v4 > 3) v4 -= 4;
v1 += n; v2 += n; v3 += n; v4 += n;
odp[l[i].ind][e - 1] = true;
if (!je(v1, v2) && !je(v1, v3) && !je(v1, v4)) {
int qwe = (2 + e - 1);
if (qwe > 4) qwe -= 4;
odp[l[i].ind][qwe - 1] = true;;
}
if (!je(v2, v3) && !je(v2, v4) && !je(v1, v3) && !je(v1, v4)) {
int qwe = (3 + e - 1);
if (qwe > 4) qwe -= 4;
odp[l[i].ind][qwe - 1] = true;
}
if (!je(v4, v1) && !je(v4, v2) && !je(v4, v3)) {
int qwe = (4 + e - 1);
if (qwe > 4) qwe -= 4;
odp[l[i].ind][qwe - 1] = true;
}
}
For(i, m) {
For(j, odp[i].size()) {
if (!odp[i][j]) continue;
cout << j + 1;
}
cout << '\n';
}
return 0;
}