제출 #1326458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326458		qwertzztrewq	Park (BOI16_park)	C++20	100 / 100	241 ms	38840 KiB

park

#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define fst first
#define snd second

template <typename t>
using vv = vector<t>;
template <typename a, typename b>
using pp = pair<a, b>;

typedef long long ll;
typedef double db;

const int mod = 1e9 + 7;

vv<int> rep, s;

int fnd(int node) {
    if (rep[node] == node) return node;
    return rep[node] = fnd(rep[node]);
}

void unite(int u, int v) {
    if (u == v) return;
    if (s[u] < s[v]) swap(u, v);
    s[u] += s[v];
    rep[v] = u;
}

db sq(db x) {
    return x * x;
}

ll lsq(ll x) {
    return x * x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n, m, w, h;
    cin >> n >> m >> w >> h;
    vv<pp<pp<ll, ll>, ll>> tree(n);
    vv<pp<pp<ll, int>, int>> vis(m);
    vv<string> ans(m);
    s.assign(n + 4, 1);
    rep.resize(n + 4);
    for (int i = 0; i < n + 4; i++) rep[i] = i;
    for (int i = 0; i < n; i++) cin >> tree[i].fst.fst >> tree[i].fst.snd >> tree[i].snd;
    for (int i = 0; i < m; i++) {
        cin >> vis[i].fst.fst >> vis[i].fst.snd;
        vis[i].snd = i;
    }
    sort(all(vis));
    vv<pp<ll, pp<int, int>>> edges;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            db dis = sqrt(sq(tree[i].fst.fst - tree[j].fst.fst) + sq(tree[i].fst.snd - tree[j].fst.snd)) - tree[i].snd - tree[j].snd;
            ll mxr = dis / 2;
            while (lsq(2 * mxr + 2 + tree[i].snd + tree[j].snd) <= lsq(tree[i].fst.fst - tree[j].fst.fst) + lsq(tree[i].fst.snd - tree[j].fst.snd)) mxr++;
            edges.pb({mxr, {i, j}});
        }
        ll r = tree[i].snd, mxr = (tree[i].fst.fst - r) / 2;
        edges.pb({mxr, {i, n}});
        mxr = (w - tree[i].fst.fst - r) / 2;
        edges.pb({mxr, {i,  n + 1}});
        mxr = (tree[i].fst.snd - r) / 2;
        edges.pb({mxr, {i, n + 2}});
        mxr = (h - tree[i].fst.snd - r) / 2;
        edges.pb({mxr, {i, n + 3}});
    }
    sort(all(edges));
    int p = 0;
    for (int i = 0; i < m; i++) {
        while (p < edges.size() && edges[p].fst < vis[i].fst.fst) {
            unite(fnd(edges[p].snd.fst), fnd(edges[p].snd.snd));
            p++;
        }
        int r1 = fnd(n), r2 = fnd(n + 1), r3 = fnd(n + 2), r4 = fnd(n + 3);
        vv aaa(n, true);
        int e = vis[i].fst.snd;
        if (e == 1) {
            if (r1 == r3) aaa[1] = aaa[2] = aaa[3] = false;
            if (r1 == r2) aaa[2] = aaa[3] = false;
            if (r1 == r4) aaa[3] = false;
            if (r2 == r3) aaa[1] = false;
            if (r2 == r4) aaa[2] = false;
            if (r3 == r4) aaa[1] = aaa[2] = false;
        }
        else if (e == 2) {
            if (r1 == r2) aaa[2] = aaa[3] = false;
            if (r1 == r3) aaa[0] = false;
            if (r1 == r4) aaa[3] = false;
            if (r2 == r3) aaa[0] = aaa[0] = aaa[2] = aaa[3] = false;
            if (r2 == r4) aaa[2] = false;
            if (r3 == r4) aaa[0] = aaa[3] = false;
        }
        else if (e == 3) {
            if (r1 == r2) aaa[0] = aaa[1] = false;
            if (r1 == r3) aaa[0] = false;
            if (r1 == r4) aaa[3] = false;
            if (r2 == r3) aaa[1] = false;
            if (r2 == r4) aaa[0] = aaa[1] = aaa[3] = false;
            if (r3 == r4) aaa[0] = aaa[3] = false;
        }
        else if (e == 4) {
            if (r1 == r2) aaa[0] = aaa[1] = false;
            if (r1 == r3) aaa[0] = false;
            if (r1 == r4) aaa[0] = aaa[1] = aaa[2] = false;
            if (r2 == r3) aaa[1] = false;
            if (r2 == r4) aaa[2] = false;
            if (r3 == r4) aaa[1] = aaa[2] = false;
        }
        for (int j = 0; j < 4; j++) if (aaa[j]) ans[vis[i].snd].pb(j + '1');
    }
    for (auto x : ans) cout << x << "\n";
    return 0;
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42