oj.uz

Submission #1106737

# Submission time Handle Problem Language Result Execution time Memory
1106737 2024-10-31T02:16:44 Z nguyenkhangninh99 Park (BOI16_park) C++14
100 / 100
 316 ms 135084 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long


struct pot{
    int x, y, r;
} arr[2001];
int ans[100001];
int par[3001];
int sz[3001];
int find_par(int x){
    return (x == par[x] ? x : par[x] = find_par(par[x]));
}

void uni(int a,int b){
    a = find_par(a);
    b = find_par(b);
    if(a != b){
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
    }
}
vector<array<int, 4>> sweep;
int w, h, n, m;
int dist(pot a, pot b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) - a.r - b.r;
}
bool check(int st, int ed){
    if(st > ed) swap(st, ed);

    if(st == ed) return true;

    if(st == 1){
        if(ed == 2){
            if(find_par(n + 1) == find_par(n + 3)) return 0;
            if(find_par(n + 2) == find_par(n + 3)) return 0;
            if(find_par(n + 4) == find_par(n + 3)) return 0;
        }
        if(ed == 3){
            if(find_par(n + 1) == find_par(n + 2)) return 0;
            if(find_par(n + 1) == find_par(n + 3)) return 0;
            if(find_par(n + 4) == find_par(n + 3)) return 0;
            if(find_par(n + 4) == find_par(n + 2)) return 0;
        }
        if(ed == 4){
            if(find_par(n + 1) == find_par(n + 4)) return 0;
            if(find_par(n + 2) == find_par(n + 4)) return 0;
            if(find_par(n + 3) == find_par(n + 4)) return 0;
        }
    }
    else if(st == 2){
        if(ed == 3){
            if(find_par(n + 1) == find_par(n + 2)) return 0;
            if(find_par(n + 2) == find_par(n + 4)) return 0;
            if(find_par(n + 2) == find_par(n + 3)) return 0;
        }
        if(ed == 4){
            if(find_par(n + 1) == find_par(n + 3)) return 0;
            if(find_par(n + 2) == find_par(n + 3)) return 0;
            if(find_par(n + 1) == find_par(n + 4)) return 0;
            if(find_par(n + 4) == find_par(n + 2)) return 0;
        }
    }
    else{
        if(find_par(n + 1) == find_par(n + 3)) return 0;
        if(find_par(n + 2) == find_par(n + 1)) return 0;
        if(find_par(n + 4) == find_par(n + 1)) return 0;
    }
    return 1;
}

void solve(){
    cin >> n >> m >> w >> h;
    for(int i = 1; i <= n; i++){
        int a, b, r; cin >> a >> b >> r;
        arr[i] = {a, b, r};
        sweep.push_back({h - b - r, 1, i, n + 1});
        sweep.push_back({w - a - r, 1, i, n + 2});
        sweep.push_back({b - r, 1, i, n + 3});
        sweep.push_back({a - r, 1, i, n + 4});
    }

    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            sweep.push_back({dist(arr[i], arr[j]), 1, i, j});
        }
    }

    for(int i = 1; i <= n + 4; i++){
        sz[i] = 1;
        par[i] = i;
    }
    for(int i = 1; i <= m; i++){
        int r, st; cin >> r >> st;
        sweep.push_back({2 * r, 0, st, i});
    }

    sort(sweep.begin(), sweep.end());

    for(array<int, 4> i: sweep){
        int type = i[1], u = i[2], v = i[3];

        if(type) uni(u, v);
        else{
            for(int j = 1; j <= 4; j++){
                if(check(u, j)){
                    ans[v] = ans[v] * 10 + j;
                }
            }
        }
    }
    
    for(int i = 1; i <= m; i++) cout << ans[i] << "\n";
}


 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    solve();
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 68280 KB Output is correct
2 Correct 262 ms 68280 KB Output is correct
3 Correct 256 ms 68424 KB Output is correct
4 Correct 258 ms 68272 KB Output is correct
5 Correct 287 ms 68280 KB Output is correct
6 Correct 261 ms 68280 KB Output is correct
7 Correct 243 ms 68280 KB Output is correct
8 Correct 250 ms 68280 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7368 KB Output is correct
2 Correct 37 ms 7368 KB Output is correct
3 Correct 35 ms 7388 KB Output is correct
4 Correct 35 ms 7368 KB Output is correct
5 Correct 36 ms 7380 KB Output is correct
6 Correct 35 ms 7368 KB Output is correct
7 Correct 33 ms 7772 KB Output is correct
8 Correct 34 ms 7624 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 68280 KB Output is correct
2 Correct 262 ms 68280 KB Output is correct
3 Correct 256 ms 68424 KB Output is correct
4 Correct 258 ms 68272 KB Output is correct
5 Correct 287 ms 68280 KB Output is correct
6 Correct 261 ms 68280 KB Output is correct
7 Correct 243 ms 68280 KB Output is correct
8 Correct 250 ms 68280 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 37 ms 7368 KB Output is correct
12 Correct 37 ms 7368 KB Output is correct
13 Correct 35 ms 7388 KB Output is correct
14 Correct 35 ms 7368 KB Output is correct
15 Correct 36 ms 7380 KB Output is correct
16 Correct 35 ms 7368 KB Output is correct
17 Correct 33 ms 7772 KB Output is correct
18 Correct 34 ms 7624 KB Output is correct
19 Correct 290 ms 135080 KB Output is correct
20 Correct 316 ms 134844 KB Output is correct
21 Correct 298 ms 135056 KB Output is correct
22 Correct 307 ms 134956 KB Output is correct
23 Correct 300 ms 135004 KB Output is correct
24 Correct 276 ms 135084 KB Output is correct