제출 #1024257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1024257		kirakaminski968	Park (BOI16_park)	C++17	100 / 100	215 ms	35528 KiB

park

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define ms(x, a) memset(x, a, sizeof(x))
//==================================
const int MAX = 2023;
ll x[MAX], y[MAX], r[MAX], p[MAX], gone[5][5];
struct E{ int a, b; ll w; };

int findP(int a){ return p[a] < 0? a : p[a] = findP(p[a]); }
void unite(int a, int b){
    a = findP(a), b = findP(b);
    if (a == b) return;
    if (p[a] > p[b]) swap(a, b);
    p[a] += p[b], p[b] = a;
}

inline bool f(int a, int b, ll R){ return gone[a][b] < R; }

int main(){
    cin.tie(0)->sync_with_stdio(0);
    ll n, q, W, H; cin >> n >> q >> W >> H;
    vector<E> ee;
    for (int i = 5; i <= n+4; i++){
        cin >> x[i] >> y[i] >> r[i];
        ee.pb({1, i, H-y[i]-r[i]});
        ee.pb({2, i, W-x[i]-r[i]});
        ee.pb({3, i, y[i]-r[i]});
        ee.pb({4, i, x[i]-r[i]});
        for (int j = 5; j < i; j++){
            ee.pb({j, i, (ll)(sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j])});
        }
    }
    sort(all(ee), [](const E &i, const E &j){ return i.w < j.w; });
    ms(gone, -1); ms(p, -1);
    for (auto[a, b, w]: ee){
        unite(a, b);
        for (int i = 1; i <= 4; i++){
            for (int j = i+1; j <= 4; j++){
                if (gone[i][j] == -1 && findP(i) == findP(j)) gone[i][j] = gone[j][i] = w;
            }
        }
    }
    while (q--){
        ll R, pp; cin >> R >> pp; R *= 2;
        vector<bool> ok(5, 1);
        if (pp == 1){
            if (f(3, 4, R)) ok[2] = ok[3] = ok[4] = 0; //Lower left
            if (f(4, 1, R)) ok[4] = 0; //Upper left
            if (f(1, 2, R)) ok[3] = 0; //Upper right
            if (f(2, 3, R)) ok[2] = 0; //Lower right
            if (f(1, 3, R)) ok[2] = ok[3] = false; // Vert
            if (f(2, 4, R)) ok[4] = ok[3] = false; //Horz
        } else if (pp == 2){
            if (f(3, 4, R)) ok[1] = 0; //Lower left
            if (f(4, 1, R)) ok[4] = 0; //Upper left
            if (f(1, 2, R)) ok[3] = 0; //Upper right
            if (f(2, 3, R)) ok[1] = ok[3] = ok[4] = 0; //Lower right
            if (f(1, 3, R)) ok[1] = ok[4] = false; // Vert
            if (f(2, 4, R)) ok[4] = ok[3] = false; //Horz
        } else if (pp == 3){
            if (f(3, 4, R)) ok[1] = 0; //Lower left
            if (f(4, 1, R)) ok[4] = 0; //Upper left
            if (f(1, 2, R)) ok[1] = ok[2] = ok[4] = 0; //Upper right
            if (f(2, 3, R)) ok[2] = 0; //Lower right
            if (f(1, 3, R)) ok[1] = ok[4] = false; // Vert
            if (f(2, 4, R)) ok[1] = ok[2] = false; //Horz
        } else {
            if (f(3, 4, R)) ok[1] = 0; //Lower left
            if (f(4, 1, R)) ok[1] = ok[2] = ok[3] = 0; //Upper left
            if (f(1, 2, R)) ok[3] = 0; //Upper right
            if (f(2, 3, R)) ok[2] = 0; //Lower right
            if (f(1, 3, R)) ok[2] = ok[3] = false; // Vert
            if (f(2, 4, R)) ok[1] = ok[2] = false; //Horz
        }

        for (int i = 1; i <= 4; i++) if (ok[i]) cout << i;
        cout << "\n";
    }
}

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