oj.uz

Submission #1097871

# Submission time Handle Problem Language Result Execution time Memory
1097871 2024-10-08T13:27:41 Z bruh Park (BOI16_park) C++14
100 / 100
 244 ms 53844 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++;
        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

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 237 ms 49824 KB Output is correct
2 Correct 212 ms 49856 KB Output is correct
3 Correct 212 ms 49856 KB Output is correct
4 Correct 216 ms 49808 KB Output is correct
5 Correct 217 ms 49848 KB Output is correct
6 Correct 211 ms 49820 KB Output is correct
7 Correct 193 ms 49952 KB Output is correct
8 Correct 189 ms 49856 KB Output is correct
9 Correct 1 ms 1880 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 33 ms 6032 KB Output is correct
2 Correct 33 ms 7080 KB Output is correct
3 Correct 32 ms 7012 KB Output is correct
4 Correct 33 ms 7052 KB Output is correct
5 Correct 32 ms 7112 KB Output is correct
6 Correct 35 ms 7108 KB Output is correct
7 Correct 31 ms 6488 KB Output is correct
8 Correct 33 ms 6484 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 49824 KB Output is correct
2 Correct 212 ms 49856 KB Output is correct
3 Correct 212 ms 49856 KB Output is correct
4 Correct 216 ms 49808 KB Output is correct
5 Correct 217 ms 49848 KB Output is correct
6 Correct 211 ms 49820 KB Output is correct
7 Correct 193 ms 49952 KB Output is correct
8 Correct 189 ms 49856 KB Output is correct
9 Correct 1 ms 1880 KB Output is correct
10 Correct 1 ms 1884 KB Output is correct
11 Correct 33 ms 6032 KB Output is correct
12 Correct 33 ms 7080 KB Output is correct
13 Correct 32 ms 7012 KB Output is correct
14 Correct 33 ms 7052 KB Output is correct
15 Correct 32 ms 7112 KB Output is correct
16 Correct 35 ms 7108 KB Output is correct
17 Correct 31 ms 6488 KB Output is correct
18 Correct 33 ms 6484 KB Output is correct
19 Correct 244 ms 53840 KB Output is correct
20 Correct 243 ms 53644 KB Output is correct
21 Correct 241 ms 53756 KB Output is correct
22 Correct 243 ms 53692 KB Output is correct
23 Correct 243 ms 53844 KB Output is correct
24 Correct 237 ms 53844 KB Output is correct