Submission #713472

#	Time	Username	Problem	Language	Result	Execution time	Memory
713472		_martynas	Park (BOI16_park)	C++11	100 / 100	815 ms	40344 KiB

park

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 2005;
const int MXM = 1e5+5;

int n, m;
ll w, h;
ll X[MXN], Y[MXN], R[MXN];
double dist[MXN][MXN];
vector<pii> edges;
// n - down, n+1 - right, n+2 - up, n+3 - left
double connected_at[4][4];
// dsu
int par[MXN], sz[MXN];
void init() {
    iota(par, par+n+4, 0);
    fill(sz, sz+n+4, 1);
}
int find_set(int a) {
    return par[a] == a ? a : par[a] = find_set(par[a]);
}
void unite(int a, int b) {
    a = find_set(a), b = find_set(b);
    if(a == b) return;
    if(sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
}
//
int main() {
    FASTIO();
    cin >> n >> m;
    cin >> w >> h;
    for(int i = 0; i < n; i++) {
        cin >> X[i] >> Y[i] >> R[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            dist[i][j] = sqrt(1.0*(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]))-R[i]-R[j];
            edges.PB({i, j});
        }
        dist[i][n] = Y[i] - R[i];
        dist[i][n+1] = (w - X[i]) - R[i];
        dist[i][n+2] = (h - Y[i]) - R[i];
        dist[i][n+3] = X[i] - R[i];
        edges.PB({i, n});
        edges.PB({i, n+1});
        edges.PB({i, n+2});
        edges.PB({i, n+3});
    }
    sort(all(edges), [&](pii a, pii b){
        return dist[a.F][a.S] < dist[b.F][b.S];
    });
    init();
    for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) connected_at[i][j] = w*h;
    for(auto e : edges) {
        unite(e.F, e.S);
        double d = dist[e.F][e.S];
        for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) {
            if(find_set(n+i) == find_set(n+j)) {
                connected_at[i][j] = min(connected_at[i][j], d);
            }
        }
    }
//    for(int i = 0; i < 4; i++) for(int j = 0; j < 4; j++) {
//        cerr << i << " " << j << ": " << fixed << setprecision(0) << connected_at[i][j] << "\n";
//    }
    for(int i = 0; i < m; i++) {
        ll r, e; cin >> r >> e; e--;
        for(int j = 0; j < 4; j++) {
            bool ok = true;
            ok &= connected_at[e][(e+3)%4]+1e-3 >= 2*r;
            ok &= connected_at[j][(j+3)%4]+1e-3 >= 2*r;
            if((j+2)%4 == e) {
                // opposite
                ok &= connected_at[j][(j+2)%4]+1e-3 >= 2*r;
                ok &= connected_at[(j+1)%4][(j+3)%4]+1e-3 >= 2*r;
            }
            else if((j+1)%4 == e) {
                ok &= connected_at[j][(j+2)%4]+1e-3 >= 2*r;
            }
            else {
                ok &= connected_at[e][(e+2)%4]+1e-3 >= 2*r;
            }
            if(j == e) ok = true;
            if(ok) {
                cout << j+1;
            }
        }
        cout << "\n";
    }
    return 0;
}

/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

*/

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