Submission #1106737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106737		nguyenkhangninh99	Park (BOI16_park)	C++14	100 / 100	316 ms	135084 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42