oj.uz

Submission #1097833

# Submission time Handle Problem Language Result Execution time Memory
1097833 2024-10-08T09:59:21 Z HuyAT Park (BOI16_park) C++14
100 / 100
 242 ms 54184 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
#define FOR(i, a) for (int i=0; i<(a); i++)
#define all(x) x.begin(), x.end()
#define gcd __gcd
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
//const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};

struct DSU{
    vi par, sz;
    int n;
    DSU(int _n){
        n = _n;
        sz.assign(n + 1, 1);
        par.assign(n + 1, 0);
        iota(all(par), 0);
    }
    int root(int u){
        if(par[u] == u) return u;
        return par[u] = root(par[u]);
    }
    bool same(int u, int v){
        return root(u) == root(v);
    }
    void unite(int u, int v){
        u = root(u), v = root(v);
        if(u == v) return;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        par[v] = u;
    }
};

const int N = 2010;
const int NN = 1e5 + 5;

struct circle{
    int x, y, r;
    int dist(circle a){
        ld ans = (a.x - x) * (a.x - x) + (a.y - y) * (a.y - y);
        return sqrtl(ans);
    }
} c[N];

bool ans[NN][5];

struct bruh{
    int w, u, v;
    bool operator < (bruh &a) const {
        return w < a.w;
    }
};

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    int w, h; cin >> w >> h;
    for(int i = 1; i <= n; ++i) cin >> c[i].x >> c[i].y >> c[i].r;
    vector<bruh> query(m);
    int rmax = 0;
    FOR(i, m){
        int e, r; cin >> r >> e;
        r *= 2;
        rmax = max(rmax, r);
        query[i] = {r, e, i};
    }
    vector<bruh> v;
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){
            int d = c[i].dist(c[j]);
            v.push_back({d - c[i].r - c[j].r, i, j});
        }
    }
    int sz = n;
    int n1 = sz + 1, n2 = sz + 2, n3 = sz + 3, n4 = sz + 4;
    sz += 4;
    int lx = rmax, rx = w - rmax, ly = rmax, ry = h - rmax;
    for(int i = 1; i <= n; ++i){
        int x = c[i].x, y = c[i].y; ld r = c[i].r;
//        if(x - r >= lx && x + r <= rx){
            v.push_back({y - r, i, n1});
            v.push_back({h - y - r, i, n3});
//        }
//        if(y - r >= ly && y + r <= ry){
            v.push_back({x - r, i, n4});
            v.push_back({w - x - r, i, n2});
//        }
    }
    sort(all(query));
    sort(all(v));
    int j = 0, lim = v.size();
    DSU dsu(sz);
    for(auto &it : query){
        int r = it.w, e = it.u, id = it.v;
        while(j < lim && v[j].w < r){
            int U = v[j].u, V = v[j].v;
            dsu.unite(U, V);
            ++j;
        }
        for(int i = 1; i <= 4; ++i){
            if(i == e)
                continue;
            if(e == 1){
                if(dsu.same(n1, n4)) ans[id][i] = 1;
                if(i == 2) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n1, n2));
                if(i == 3) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n2, n3));
                if(i == 4) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n3, n4));
            }
            if(e == 2){
                if(dsu.same(n1, n2)) ans[id][i] = 1;
                if(i == 3) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n2, n3));
                if(i == 4) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n3, n4));
                if(i == 1) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n1, n4));
            }
            if(e == 3){
                if(dsu.same(n2, n3)) ans[id][i] = 1;
                if(i == 4) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n3, n4));
                if(i == 1) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n1, n4));
                if(i == 2) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n1, n2));
            }
            if(e == 4){
                if(dsu.same(n3, n4)) ans[id][i] = 1;
                if(i == 1) ans[id][i] |= (dsu.same(n2, n4) || dsu.same(n1, n4));
                if(i == 2) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n4) || dsu.same(n1, n2));
                if(i == 3) ans[id][i] |= (dsu.same(n1, n3) || dsu.same(n2, n3));
            }
        }
    }
    FOR(i, m){
        for(int j = 1; j <= 4; ++j) if(!ans[i][j]) cout << j;
        cout << "\n";
    }
    return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:90:28: warning: narrowing conversion of '((ld)y - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   90 |             v.push_back({y - r, i, n1});
      |                          ~~^~~
park.cpp:91:32: warning: narrowing conversion of '((ld)(h - y) - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   91 |             v.push_back({h - y - r, i, n3});
      |                          ~~~~~~^~~
park.cpp:94:28: warning: narrowing conversion of '((ld)x - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   94 |             v.push_back({x - r, i, n4});
      |                          ~~^~~
park.cpp:95:32: warning: narrowing conversion of '((ld)(w - x) - r)' from 'ld' {aka 'long double'} to 'long long int' [-Wnarrowing]
   95 |             v.push_back({w - x - r, i, n2});
      |                          ~~~~~~^~~
park.cpp:86:9: warning: unused variable 'lx' [-Wunused-variable]
   86 |     int lx = rmax, rx = w - rmax, ly = rmax, ry = h - rmax;
      |         ^~
park.cpp:86:20: warning: unused variable 'rx' [-Wunused-variable]
   86 |     int lx = rmax, rx = w - rmax, ly = rmax, ry = h - rmax;
      |                    ^~
park.cpp:86:35: warning: unused variable 'ly' [-Wunused-variable]
   86 |     int lx = rmax, rx = w - rmax, ly = rmax, ry = h - rmax;
      |                                   ^~
park.cpp:86:46: warning: unused variable 'ry' [-Wunused-variable]
   86 |     int lx = rmax, rx = w - rmax, ly = rmax, ry = h - rmax;
      |                                              ^~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 50364 KB Output is correct
2 Correct 200 ms 49896 KB Output is correct
3 Correct 203 ms 50868 KB Output is correct
4 Correct 205 ms 51648 KB Output is correct
5 Correct 199 ms 50100 KB Output is correct
6 Correct 195 ms 51388 KB Output is correct
7 Correct 187 ms 51388 KB Output is correct
8 Correct 182 ms 50756 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4052 KB Output is correct
2 Correct 33 ms 4212 KB Output is correct
3 Correct 32 ms 4184 KB Output is correct
4 Correct 32 ms 4216 KB Output is correct
5 Correct 31 ms 4192 KB Output is correct
6 Correct 33 ms 4304 KB Output is correct
7 Correct 27 ms 3412 KB Output is correct
8 Correct 29 ms 3420 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 50364 KB Output is correct
2 Correct 200 ms 49896 KB Output is correct
3 Correct 203 ms 50868 KB Output is correct
4 Correct 205 ms 51648 KB Output is correct
5 Correct 199 ms 50100 KB Output is correct
6 Correct 195 ms 51388 KB Output is correct
7 Correct 187 ms 51388 KB Output is correct
8 Correct 182 ms 50756 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 34 ms 4052 KB Output is correct
12 Correct 33 ms 4212 KB Output is correct
13 Correct 32 ms 4184 KB Output is correct
14 Correct 32 ms 4216 KB Output is correct
15 Correct 31 ms 4192 KB Output is correct
16 Correct 33 ms 4304 KB Output is correct
17 Correct 27 ms 3412 KB Output is correct
18 Correct 29 ms 3420 KB Output is correct
19 Correct 242 ms 52600 KB Output is correct
20 Correct 234 ms 53184 KB Output is correct
21 Correct 236 ms 53656 KB Output is correct
22 Correct 238 ms 52792 KB Output is correct
23 Correct 234 ms 54184 KB Output is correct
24 Correct 219 ms 53184 KB Output is correct