Submission #164536

#	Time	Username	Problem	Language	Result	Execution time	Memory
164536		nvmdava	Park (BOI16_park)	C++17	100 / 100	686 ms	74428 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL
#define N 2005

vector<pair<long double, pair<int, int > > > dist, q;

int p[N];
long double x[N], y[N], r[N];

inline long double sq(long double w){
    return w * w;
}

int find(int v){
    return v == p[v] ? v : p[v] = find(p[v]);
}

void unite(int v, int u){
    v = find(v);
    u = find(u);
    p[v] = u;
}

vector<int> ans[100005];

bool check(int v, int u){
    if(v == u) return 1;
    find(1);
    find(2);
    find(3);
    find(4);
    if(v > u) swap(v, u);
    swap(v, u);
    if(v == 1 && p[1] == p[2])
        return 0;
    if(v == 2 && p[2] == p[3])
        return 0;
    if(v == 3 && p[4] == p[3])
        return 0;
    if(v == 4 && p[4] == p[1])
        return 0;
    swap(v, u);
    if(v == 1 && p[1] == p[2])
        return 0;
    if(v == 2 && p[2] == p[3])
        return 0;
    if(v == 3 && p[4] == p[3])
        return 0;
    if(v == 4 && p[4] == p[1])
        return 0;
    if(v == 1){
        if(u == 2){
            if(p[2] == p[4])
                return 0;
            return 1;
        }
        if(u == 3){
            if(p[2] == p[4] || p[1] == p[3])
                return 0;
            return 1;
        }
        if(u == 4){
            if(p[1] == p[3])
                return 0;
            return 1;
        }
    }
    if(v == 3){
        if(u == 4){
            if(p[2] == p[4])
                return 0;
            return 1;
        }
    }
    if(v == 2){
        if(u == 3){
            if(p[1] == p[3])
                return 0;
            return 1;
        }
        if(u == 4){
            if(p[1] == p[3] || p[2] == p[4])
                return 0;
            return 1;
        }
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, w, h;
    cin>>n>>m;
    cin>>w>>h;
    for(int i = n + 4; i > 0; --i)
        p[i] = i;
    for(int i = n + 4; i > 4; --i){
        cin>>x[i]>>y[i]>>r[i];
        for(int j = n + 4; j > i; --j){
            double d = sqrt(sq(x[i] - x[j]) + sq(y[i] - y[j]));
            d -= r[i] + r[j];
            dist.push_back({d, {i, j}});
        }
        dist.push_back({x[i] - r[i], {1, i}});
        dist.push_back({y[i] - r[i], {2, i}});
        dist.push_back({w - x[i] - r[i], {3, i}});
        dist.push_back({h - y[i] - r[i], {4, i}});
    }
    sort(dist.rbegin(), dist.rend());
    for(int i = 1; i <= m; i++){
        int R, E;
        cin>>R>>E;
        R *= 2;
        q.push_back({R, {i, E}});
    }
    sort(q.begin(), q.end());
    for(auto& Q : q){
        while(!dist.empty() && dist.back().ff < Q.ff){
            unite(dist.back().ss.ff, dist.back().ss.ss);
            dist.pop_back();
        }
        for(int i = 1; i <= 4; i++){
            if(check(i, Q.ss.ss)){
                ans[Q.ss.ff].push_back(i);
            }
        }
    }

    for(int i = 1; i <= m; i++){
        sort(ans[i].begin(), ans[i].end());
        for(auto& x : ans[i])
            cout<<x;
        cout<<'\n';
    }
}

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