oj.uz

Submission #713470

# Submission time Handle Problem Language Result Execution time Memory
713470 2023-03-22T07:22:45 Z _martynas Park (BOI16_park) C++11
0 / 100
 746 ms 39064 KB 
#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 << ": " << 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] >= 2*r;
            ok &= connected_at[j][(j+3)%4] >= 2*r;
            if((j+2)%4 == e) {
                // opposite
                ok &= connected_at[j][(j+2)%4] >= 2*r;
                ok &= connected_at[(j+1)%4][(j+3)%4] >= 2*r;
            }
            else if((j+1)%4 == e) {
                ok &= connected_at[j][(j+2)%4] >= 2*r;
            }
            else {
                ok &= connected_at[e][(e+2)%4] >= 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 38932 KB Output is correct
2 Correct 708 ms 39024 KB Output is correct
3 Correct 746 ms 39064 KB Output is correct
4 Correct 746 ms 38996 KB Output is correct
5 Correct 716 ms 38992 KB Output is correct
6 Correct 735 ms 39064 KB Output is correct
7 Correct 474 ms 38980 KB Output is correct
8 Correct 460 ms 38984 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2152 KB Output is correct
2 Correct 34 ms 2020 KB Output is correct
3 Correct 33 ms 2096 KB Output is correct
4 Correct 33 ms 2136 KB Output is correct
5 Correct 33 ms 2108 KB Output is correct
6 Correct 36 ms 2100 KB Output is correct
7 Incorrect 27 ms 596 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 38932 KB Output is correct
2 Correct 708 ms 39024 KB Output is correct
3 Correct 746 ms 39064 KB Output is correct
4 Correct 746 ms 38996 KB Output is correct
5 Correct 716 ms 38992 KB Output is correct
6 Correct 735 ms 39064 KB Output is correct
7 Correct 474 ms 38980 KB Output is correct
8 Correct 460 ms 38984 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -