제출 #1250567

#제출 시각아이디문제언어결과실행 시간메모리
1250567bruhhhhPark (BOI16_park)C++20
100 / 100
331 ms49900 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007; const ll INF = 4e18; ll z[4][4], f[4][4]; struct DSU { ll par[5000], sz[5000]; DSU() { for (int i = 0; i < 5000; i++) { par[i] = i; sz[i] = 1; } } ll get(ll x) { return (par[x] == x ? x : par[x] = get(par[x])); } void cmb(ll x, ll y) { x = get(x); y = get(y); if (x == y) { return; } if (sz[x] < sz[y]) { swap(x, y); } par[y] = x; sz[x] += sz[y]; } }; ll cntdist(ll x, ll y){ return floor(sqrtl(x * x + y * y)); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m, w, h; cin >> n >> m >> w >> h; vector<ll> a(n + 1), b(n + 1), c(n + 1); vector<array<ll, 3>> edges; for (int i = 0; i < 4; i++) { fill(z[i], z[i] + 4, INF); fill(f[i], f[i] + 4, INF); } for (int i = 0; i < n; i++) { cin >> a[i] >> b[i] >> c[i]; ll g = i + 4; for (int j = 0; j < i; j++){ edges.push_back({cntdist(a[i] - a[j], b[i] - b[j]) - c[i] - c[j], g, j + 4}); } edges.push_back({a[i] - c[i], 0, g}); edges.push_back({b[i] - c[i], 1, g}); edges.push_back({w - a[i] - c[i], 2, g}); edges.push_back({h - b[i] - c[i], 3, g}); } sort(edges.begin(), edges.end()); DSU Wibu; for (auto &e : edges){ Wibu.cmb(e[1], e[2]); for (int x = 0; x < 4; x++) { for (int y = 0; y < 4; y++) { if (Wibu.get(x) == Wibu.get(y)) { z[x][y] = min(z[x][y], e[0]); } } } } auto add = [&](int u, int v, initializer_list<ll> vals) { ll mn = *min_element(vals.begin(), vals.end()); f[u][v] = f[v][u] = mn; }; add(0, 1, {z[1][3], z[1][0], z[1][2]}); add(2, 3, {z[3][0], z[3][1], z[3][2]}); add(0, 3, {z[0][1], z[0][2], z[0][3]}); add(1, 2, {z[2][1], z[2][0], z[2][3]}); add(0, 2, {z[1][3], z[0][2], z[0][1], z[2][3]}); add(1, 3, {z[1][2], z[0][3], z[1][3], z[0][2]}); while(m--){ ll x, y; cin >> x >> y; y--; for (int i = 0; i < 4; i++){ if (2 * x <= f[y][i]) { cout << i + 1; } } cout << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...