Submission #1097812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097812		bruh	Park (BOI16_park)	C++14	0 / 100	457 ms	57500 KiB

park

#include<bits/stdc++.h>
#define int long long
#define ld long double

using namespace std;
const int maxn = 2e5 + 5;
int n, m, w,h, q;
int par[maxn], ans[maxn], x[maxn], y[maxn], r[maxn];
array<int, 3> qr[maxn];
struct iii{
    int x;
    int y, z;
    bool operator < (iii b) const{
        return x < b.x;
    }
};

vector<iii> edges;
int root(int x)
{
    return par[x] < 0 ? x : par[x] = root(par[x]);
}

bool unite(int u, int v)
{
    if ((u = root(u)) == (v = root(v))) return 0;
    if (par[u] > par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;
    return 1;
}

bool same(int u, int v)
{
    return root(u) == root(v);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> q;
    cin >> w >> h;
    int w0 = n + 1, w1 = n + 2, h0 = n + 3, h1 = n + 4;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i] >> r[i];
        edges.push_back({x[i] - r[i], w0, i});
        edges.push_back({w - x[i] - r[i], w1, i});
        edges.push_back({y[i] - r[i], h0, i});
        edges.push_back({h - y[i] - r[i], h1, i});
    }
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            int dis = (int)sqrt(1.0 * (x[i] - x[j]) * (x[i] - x[j]) + 1.0 * (y[i] - y[j]) * (y[i] - y[j])) - (ld)r[i] - (ld)r[j];
            edges.push_back({dis, i, j});
        }
    for (int i = 1; i <= q; i++)
        cin >> qr[i][0] >> qr[i][1], qr[i][2] = i;
    sort(qr + 1, qr + q + 1);
    sort(edges.begin(), edges.end());
    memset(par, -1, sizeof par);
    for (int i = 1, pt = 0; i <= q; i++)
    {
        while (pt < edges.size() && edges[pt].x < (ld)2 * qr[i][0])
            unite(edges[pt].y, edges[pt].z),
            pt++;
        if (qr[i][1] == 1)
        {
            ans[qr[i][2]] = (1 << 4) - 1;
            if (same(h0, h1) || same(w0, h1) || same(w1, h1)) ans[qr[i][2]] ^= 1 << 1;
            if (same(h0, h1) || same(w0, w1) || same(w0, h1) || same(w1, h0)) ans[qr[i][2]] ^= 1 << 2;
            if (same(w0, w1) || same(w0, h1) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 3;
        }
        if (qr[i][1] == 2)
        {
            ans[qr[i][2]] = (1 << 4) - 1;
            if (same(h0, h1) || same(w1, h1) || same(w0, h1)) ans[qr[i][2]] ^= 1 << 0;
            if (same(w0, w1) || same(w1, h1) || same(h0, w1)) ans[qr[i][2]] ^= 1 << 2;
            if (same(h0, h1) || same(w0, w1) || same(w1, h1) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 3;
        }
        if (qr[i][1] == 3)
        {
            ans[qr[i][2]] = (1 << 4) - 1;
            if (same(h0, h1) || same(w0, w1) || same(w0, h1) || same(w1, h0)) ans[qr[i][2]] ^= 1 << 0;
            if (same(w0, w1) || same(w1, h1) || same(h0, w1)) ans[qr[i][2]] ^= 1 << 1;
            if (same(h0, h1) || same(w0, h0) || same(h0, w1)) ans[qr[i][2]] ^= 1 << 3;
        }
        if (qr[i][1] == 4)
        {
            ans[qr[i][2]] = (1 << 4) - 1;
            if (same(w0, w1) || same(w0, h0) || same(w0, h1)) ans[qr[i][2]] ^= 1 << 0;
            if (same(h0, h1) || same(w0, w1) || same(w1, h1) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 1;
            if (same(h0, h1) || same(h0, w1) || same(h0, w0)) ans[qr[i][2]] ^= 1 << 2;
        }
    }
    for (int i = 1; i <= q; i++)
    {
        int x = ans[i];
        for (int j = 0; j < 4; j++)
            if (x >> j & 1)
                cout << j + 1;
        cout << "\n";
    }
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:68:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<iii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         while (pt < edges.size() && edges[pt].x < (ld)2 * qr[i][0])
      |                ~~~^~~~~~~~~~~~~~

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