Submission #713400

#	Time	Username	Problem	Language	Result	Execution time	Memory
713400		stevancv	Park (BOI16_park)	C++14	100 / 100	277 ms	29564 KiB

park

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2500 + 5;
const int M = 1e5 + 5;
const int inf = 1e9;
struct Dsu {
    int p[N];
    void Init(int n) {
        for (int i = 0; i < n; i++) p[i] = i;
    }
    int Find(int x) {
        if (x == p[x]) return x;
        return p[x] = Find(p[x]);
    }
    void Unite(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) return;
        p[v] = u;
    }
    int Same(int u, int v) {
        return Find(u) == Find(v);
    }
}dsu;
int Dist(ll xa, ll ya, ll xb, ll yb) {
    ll o = (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);
    o = sqrt(o);
    return o;
}
int sol[M][4];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, h, w;
    cin >> n >> m >> w >> h;
    vector<array<int, 3>> e;
    vector<int> X(n), Y(n), R(n);
    for (int i = 0; i < n; i++) {
        cin >> X[i] >> Y[i] >> R[i];
        int x = X[i]; int y = Y[i]; int r = R[i];
        e.push_back({i, n, max(0, y - r)});
        e.push_back({i, n + 1, max(0, w - x - r)});
        e.push_back({i, n + 2, max(0, h - y - r)});
        e.push_back({i, n + 3, max(0, x - r)});
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            e.push_back({i, j, max(0, Dist(X[i], Y[i], X[j], Y[j]) - R[i] - R[j])});
        }
    }
    sort(e.begin(), e.end(), [&] (array<int, 3> i, array<int, 3> j) {
        return i[2] < j[2];
    });
    vector<array<int, 3>> qq;
    for (int i = 0; i < m; i++) {
        int r, b;
        cin >> r >> b;
        b -= 1;
        qq.push_back({2 * r, b, i});
    }
    sort(qq.begin(), qq.end());
    int j = 0;
    dsu.Init(n + 4);
    for (auto u : qq) {
        int r = u[0]; int b = u[1]; int i = u[2];
        while (j < e.size() && e[j][2] < r) {
            dsu.Unite(e[j][0], e[j][1]);
            j += 1;
        }
        sol[i][b] = 1;
        int x = b + n; int y = (b + 1) % 4 + n; int z = (b + 2) % 4 + n; int w = (b + 3) % 4 + n;
        if (!dsu.Same(x, y) && !dsu.Same(x, z) && !dsu.Same(x, w)) sol[i][(b + 1) % 4] = 1;
        if (!dsu.Same(x, z) && !dsu.Same(x, w) && !dsu.Same(y, z) && !dsu.Same(y, w)) sol[i][(b + 2) % 4] = 1;
        if (!dsu.Same(x, w) && !dsu.Same(y, w) && !dsu.Same(z, w)) sol[i][(b + 3) % 4] = 1;
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 4; j++) {
            if (sol[i][j]) cout << j + 1;
        }
        cout << en;
    }
    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         while (j < e.size() && e[j][2] < r) {
      |                ~~^~~~~~~~~~

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