Submission #1097871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097871		bruh	Park (BOI16_park)	C++14	100 / 100	244 ms	53844 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((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - r[i] - 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 < 2 * qr[i][0])
            unite(edges[pt].y, edges[pt].z),
            pt++;
        bool go1 = true;
            bool go2 = true;
            bool go3 = true;
            bool go4 = true;
        if(qr[i][1] == 1){
                // Vertical
                if(same(h0, h1)) go2 = go3 = false;
                if(same(h0, w0)) go2 = go4 = go3 = false;
                // Horizontal
                if(same(w1, w0)) go4 = go3 = false;
                if(same(h0, w1)) go2 = false;
                if(same(w1, h1)) go3 = false;
                if(same(h1, w0)) go4 = false;
            } else if(qr[i][1] == 2){
                // Vertical
                if(same(h0, h1)) go1 = go4 = false;
                if(same(h0, w1)) go1 = go3 = go4 = false;
                // Horizontal
                if(same(w1, w0)) go4 = go3 = false;
                if(same(h0, w0)) go1 = false;
                if(same(w1, h1)) go3 = false;
                if(same(h1, w0)) go4 = false;
            } else if(qr[i][1] == 3){
                if(same(h0, h1)) go1 = go4 = false;
                if(same(w1, w0)) go1 = go2 = false;
                if(same(w1, h1)) go1 = go2 = go4 = false;
                if(same(h0, w0)) go1 = false;
                if(same(h0, w1)) go2 = false;
                if(same(h1, w0)) go4 = false;
            } else{
                if(same(h0, h1)) go2 = go3 = false;
                if(same(w1, w0)) go1 = go2 = false;
                if(same(h1, w0)) go1 = go3 = go2 = false;
                if(same(h0, w0)) go1 = false;
                if(same(h0, w1)) go2 = false;
                if(same(w1, h1)) go3 = false;
            }
        if (go1) ans[qr[i][2]] += 1;
        if (go2) ans[qr[i][2]] += 2;
        if (go3) ans[qr[i][2]] += 4;
        if (go4) ans[qr[i][2]] += 8;
    }
    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 < 2 * qr[i][0])
      |                ~~~^~~~~~~~~~~~~~

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