Submission #529305

#	Time	Username	Problem	Language	Result	Execution time	Memory
529305		rainliofficial	Park (BOI16_park)	C++17	100 / 100	361 ms	53812 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define sz(x) (int)x.size()
#define f first
// #define s second

struct circle{
    int x, y, r, id;
};

struct edge{
    int from, to;
    double l;
};
struct person{
    int s, r, id;
};
struct DSU{
    vector<int> size, parent;
    DSU(int n){
        size.resize(n, 1);
        parent.resize(n);
        for (int i=0; i<n; i++){
            parent[i] = i;
        }
    }
    int find(int a){
        if (parent[a] == a){
            return a;
        }
        return parent[a] = find(parent[a]);
    }
    void join(int a, int b){  
        a = find(a);
        b = find(b);
        if (a == b){
            // Same component
            return;
        }
        if (size[a] < size[b]){
            // Point a to b
            parent[a] = b;
            size[b] += size[a];
        }else{
            // Point b to a
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

const int MAXN = 2000+5, MAXM = 1e5+5, L = 0, D = 1, R = 2, U = 3;
int n, m, w, h;
circle arr[MAXN];
person vis[MAXM];

double dist(int a, int b){
    if (a < 4 && b < 4){
        return -1;
    }
    if (a < 4){
        if (arr[a].x == -1){
            return abs(arr[a].y - arr[b].y) - arr[b].r;
        }else{
            return abs(arr[a].x - arr[b].x) - arr[b].r;
        }
    }else if (b < 4){
        if (arr[b].x == -1){
            return abs(arr[b].x -arr[a].y) - arr[a].r;
        }else{
            return abs(arr[b].y - arr[a].x) - arr[a].r;
        }
    }
    return sqrt((ll)(arr[a].x - arr[b].x)*(arr[a].x - arr[b].x) + (ll)(arr[a].y - arr[b].y)*(arr[a].y - arr[b].y)) - arr[a].r - arr[b].r;
}

int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file2.out", "w", stdout);
    cin >> n >> m >> w >> h;
    n += 4;
    arr[0] = {0, -1, 0, 0};
    arr[1] = {-1, 0, 0, 1};
    arr[2] = {w, -1, 0, 2};
    arr[3] = {-1, h, 0, 3};
    for (int i=4; i<n; i++){
        int x, y, r;
        cin >> x >> y >> r;
        arr[i] = {x, y, r, i};
    }
    vector<edge> edges;
    for (int i=0; i<n; i++){
        for (int j=i+1; j<n; j++){
            if (i < 4 && j < 4){
                continue;
            }
            edges.push_back({i, j, dist(i, j)});
        }
    }
    sort(edges.begin(), edges.end(), [](const edge& a, const edge& b){
        return a.l < b.l;
    });
    // for (int i=0; i<sz(edges); i++){
    //     cout << edges[i].from << " " << edges[i].to << " " << edges[i].l << "\n";
    // }
    for (int i=0; i<m; i++){
        int x, r;
        cin >> r >> x;
        vis[i] = {x, r, i};
    }
    sort(vis, vis+m, [](const person& a, const person& b) {return a.r < b.r;});
    // for (int i=0; i<m; i++){
    //     cout << vis[i].f << " " << vis[i].s << "\n";
    // }
    int e = 0;
    vector<set<int>> output(m);
    DSU dsu(n);
    for (int i=0; i<m; i++){
        while (e < sz(edges) && edges[e].l < 2*vis[i].r){
            dsu.join(edges[e].from, edges[e].to);
            // cout << edges[e].from << " " << edges[e].to << "\n";
            e++;
        }
        set<int> ans;
        ans.insert(vis[i].s);
        if (dsu.find(U) != dsu.find(D)){
            if (vis[i].s == 1 && dsu.find(D) != dsu.find(R) && dsu.find(D) != dsu.find(L)){
                ans.insert(2);
            }else if (vis[i].s == 2 && dsu.find(D) != dsu.find(L) && dsu.find(D) != dsu.find(R)){
                ans.insert(1);
            }else if (vis[i].s == 3 && dsu.find(L) != dsu.find(U) && dsu.find(U) != dsu.find(R)){
                ans.insert(4);
            }else if (vis[i].s == 4 && dsu.find(U) != dsu.find(R) && dsu.find(U) != dsu.find(L)){
                ans.insert(3);
            }
        }
        if (dsu.find(L) != dsu.find(R)){
            if (vis[i].s == 1 && dsu.find(L) != dsu.find(U)&& dsu.find(D) != dsu.find(L)){
                ans.insert(4);
            }else if (vis[i].s == 2 && dsu.find(R) != dsu.find(U) && dsu.find(D) != dsu.find(R)){
                ans.insert(3);
            }else if (vis[i].s == 3 && dsu.find(D) != dsu.find(R)&& dsu.find(U) != dsu.find(R)){
                ans.insert(2);
            }else if (vis[i].s == 4 && dsu.find(D) != dsu.find(L) && dsu.find(U) != dsu.find(L)){
                ans.insert(1);
            }
        }
        if (dsu.find(U) != dsu.find(D) && dsu.find(L) != dsu.find(R)){
            if (vis[i].s == 1 && dsu.find(U) != dsu.find(R) && dsu.find(D) != dsu.find(L)){
                ans.insert(3);
            }else if (vis[i].s == 2 && dsu.find(L) != dsu.find(U) && dsu.find(D) != dsu.find(R)){
                ans.insert(4);
            }else if (vis[i].s == 3 && dsu.find(D) != dsu.find(L) && dsu.find(U) != dsu.find(R)){
                ans.insert(1);
            }else if (vis[i].s == 4 && dsu.find(D) != dsu.find(R) && dsu.find(U) != dsu.find(L)){
                ans.insert(2);
            }
        }
        output[vis[i].id] = ans;
        // cout << "\n";
    }
    for (int i=0; i<m; i++){
        for (int j : output[i]){
            cout << j;
        }
        cout << "\n";
    }
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42