oj.uz

Submission #1097874

# Submission time Handle Problem Language Result Execution time Memory
1097874 2024-10-08T13:32:17 Z bruh Park (BOI16_park) C++14
100 / 100
 261 ms 52820 KB 
#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++;
        if (qr[i][1] == 1)
        {
            ans[qr[i][2]] = (1 << 4) - 1;
            if (same(h1, h0) || same(w0, h0) || same(w1, h0)) ans[qr[i][2]] ^= 1 << 1;
            if (same(h1, h0) || same(w0, w1) || same(w0, h0) || same(w1, h1)) ans[qr[i][2]] ^= 1 << 2;
            if (same(w0, w1) || same(w0, h0) || same(w0, h1)) ans[qr[i][2]] ^= 1 << 3;
        }
        if (qr[i][1] == 2)
        {
            ans[qr[i][2]] = (1 << 4) - 1;
            if (same(h1, h0) || same(w1, h0) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 0;
            if (same(w0, w1) || same(w1, h0) || same(h1, w1)) ans[qr[i][2]] ^= 1 << 2;
            if (same(h1, h0) || same(w0, w1) || same(w1, h0) || same(w0, h1)) ans[qr[i][2]] ^= 1 << 3;
        }
        if (qr[i][1] == 3)
        {
            ans[qr[i][2]] = (1 << 4) - 1;
            if (same(h1, h0) || same(w0, w1) || same(w0, h0) || same(w1, h1)) ans[qr[i][2]] ^= 1 << 0;
            if (same(w0, w1) || same(w1, h0) || same(h1, w1)) ans[qr[i][2]] ^= 1 << 1;
            if (same(h1, h0) || same(w0, h1) || same(h1, 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, h1) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 0;
            if (same(h1, h0) || same(w0, w1) || same(w1, h0) || same(w0, h1)) ans[qr[i][2]] ^= 1 << 1;
            if (same(h1, h0) || same(h1, w1) || same(h1, 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

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 49872 KB Output is correct
2 Correct 212 ms 49836 KB Output is correct
3 Correct 214 ms 49824 KB Output is correct
4 Correct 205 ms 49892 KB Output is correct
5 Correct 210 ms 49844 KB Output is correct
6 Correct 222 ms 49812 KB Output is correct
7 Correct 199 ms 49824 KB Output is correct
8 Correct 198 ms 49820 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6084 KB Output is correct
2 Correct 42 ms 6084 KB Output is correct
3 Correct 35 ms 6088 KB Output is correct
4 Correct 33 ms 6028 KB Output is correct
5 Correct 33 ms 6096 KB Output is correct
6 Correct 38 ms 6020 KB Output is correct
7 Correct 31 ms 5440 KB Output is correct
8 Correct 31 ms 5464 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 49872 KB Output is correct
2 Correct 212 ms 49836 KB Output is correct
3 Correct 214 ms 49824 KB Output is correct
4 Correct 205 ms 49892 KB Output is correct
5 Correct 210 ms 49844 KB Output is correct
6 Correct 222 ms 49812 KB Output is correct
7 Correct 199 ms 49824 KB Output is correct
8 Correct 198 ms 49820 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 35 ms 6084 KB Output is correct
12 Correct 42 ms 6084 KB Output is correct
13 Correct 35 ms 6088 KB Output is correct
14 Correct 33 ms 6028 KB Output is correct
15 Correct 33 ms 6096 KB Output is correct
16 Correct 38 ms 6020 KB Output is correct
17 Correct 31 ms 5440 KB Output is correct
18 Correct 31 ms 5464 KB Output is correct
19 Correct 244 ms 52820 KB Output is correct
20 Correct 261 ms 52768 KB Output is correct
21 Correct 239 ms 52816 KB Output is correct
22 Correct 241 ms 52564 KB Output is correct
23 Correct 242 ms 52816 KB Output is correct
24 Correct 239 ms 52820 KB Output is correct