Submission #1352761

#TimeUsernameProblemLanguageResultExecution timeMemory
1352761kantaponzPark (BOI16_park)C++20
100 / 100
346 ms71408 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int nx = 2009;

#define ld long double

int n, m;
long double h, w;
long double x[nx], y[nx], r[nx];
vector<tuple<long double, int, int>> Edge;
vector<tuple<long double, int, int>> visitor;
int ptr = 0;
int T, B, L, R;
bool pos[100005][5];

int pa[nx];



int fp(int n) {
    if (pa[n] == n) return n;
    return pa[n] = fp(pa[n]);
}

bool conn(int u, int v) {return fp(u) == fp(v);}

void unite(int u, int v) {
    int pu = fp(u), pv = fp(v);
    if (pu == pv) return;
    pa[pu] = pv;
}

long double dist(ld x1, ld y1, ld x2, ld y2) {
    return sqrtl((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> w >> h;
    T = n + 1, B = n + 2, L = n + 3, R = n + 4;
    for (int i = 1; i <= n + 4; i++) pa[i] = i;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> r[i];
        Edge.emplace_back(x[i] - r[i], L, i);        
        Edge.emplace_back(w - x[i] - r[i], R, i);    
        Edge.emplace_back(y[i] - r[i], B, i);        
        Edge.emplace_back(h - y[i] - r[i], T, i);   
    }
    for (int i = 1; i + 1 <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            Edge.emplace_back(dist(x[i], y[i], x[j], y[j]) - r[i] - r[j], i, j);
        }
    }
    for (int i = 1; i <= m; i++) {
        ld r;
        int e;
        cin >> r >> e;

        visitor.emplace_back(r, e, i);
    }
    sort(Edge.begin(), Edge.end());
    sort(visitor.begin(), visitor.end());

    for (int i = 0; i < m; i++) {
        auto [r, e, idx] = visitor[i];
        while (ptr < Edge.size()) {
            auto [w, u, v] = Edge[ptr];
            if (w >= 2.0 * r) break;
            unite(u, v);
            ptr++;
        }
        pos[idx][e] = 1;
        if (e == 1) {
            if (!(conn(L, B) || conn(B, R) || conn(T, B))) pos[idx][2] = 1;
            if (!(conn(L, B) || conn(L, T) || conn(L, R))) pos[idx][4] = 1;
            if (!(conn(L, B) || conn(T, R) || conn(T, B) || conn(L, R))) pos[idx][3] = 1;
        } else if (e == 2) {
            if (!(conn(L, B) || conn(B, R) || conn(T, B))) pos[idx][1] = 1;
            if (!(conn(L, R) || conn(R, T) || conn(B, R))) pos[idx][3] = 1;
            if (!(conn(L, T) || conn(B, R) || conn(T, B) || conn(L, R))) pos[idx][4] = 1;
        } else if (e == 3) {
            if (!(conn(L, R) || conn(R, T) || conn(B, R))) pos[idx][2] = 1;
            if (!(conn(T, R) || conn(L, T) || conn(T, B))) pos[idx][4] = 1;
            if (!(conn(L, B) || conn(T, R) || conn(T, B) || conn(L, R))) pos[idx][1] = 1;
        } else {
            if (!(conn(L, B) || conn(L, T) || conn(L, R))) pos[idx][1] = 1;
            if (!(conn(T, R) || conn(L, T) || conn(T, B))) pos[idx][3] = 1;
            if (!(conn(L, T) || conn(B, R) || conn(T, B) || conn(L, R))) pos[idx][2] = 1;
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int k = 1; k <= 4; k++) {
            if (pos[i][k]) cout << k;
        }
        cout << "\n";
    }

}

/*
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

1234
2
14

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...