oj.uz

Submission #1096359

# Submission time Handle Problem Language Result Execution time Memory
1096359 2024-10-04T10:55:12 Z TrinhKhanhDung Park (BOI16_park) C++14
100 / 100
 462 ms 25536 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 7)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

struct DSU{
    vector<int> par, Sz;

    DSU(int n = 0){
        par.assign(n + 3, 0);
        Sz.assign(n + 3, 1);
        iota(ALL(par), 0);
    }

    int root(int u){
        return u == par[u] ? u : par[u] = root(par[u]);
    }

    bool join(int a, int b){
        a = root(a);
        b = root(b);
        if(a == b) return false;
        if(Sz[a] < Sz[b]) swap(a, b);
        Sz[a] += Sz[b];
        par[b] = a;
        return true;
    }
};

const int maxN = 2e3 + 10, maxM = 1e5 + 10;

int N, M, W, H;
array<int, 3> trees[maxN];
int ans[10][10];
vector<array<int, 3>> edges;

ll sqr(ll a){return a * a;}

int dist(array<int, 3> a, array<int, 3> b){
    ll d = sqr(a[0] - b[0]) + sqr(a[1] - b[1]);
    return sqrtl(d) - a[2] - b[2];
}

bool OK(vector<pair<int, int>> &ord, int k){
    DSU dsu(N + 4);
    for(auto o: edges){
        int c = o[0], u = o[1], v = o[2];
        if(c >= k) break;
        dsu.join(u, v);
    }
    for(auto o: ord){
        if(dsu.root(o.fi) == dsu.root(o.se)){
            return false;
        }
    }
    return true;
}

void solve(){
    cin >> N >> M >> W >> H;
    for(int i = 1; i <= N; i++){
        int x, y, r; cin >> x >> y >> r;
        trees[i + 4] = {x, y, r};
    }
    for(int i = 5; i <= N + 4; i++){
        for(int j = i + 1; j <= N + 4; j++){
            edges.push_back({dist(trees[i], trees[j]), i, j});
        }
    }

    for(int i = 5; i <= N + 4; i++){
        edges.push_back({trees[i][1] - trees[i][2], 1, i});
        edges.push_back({W - trees[i][0] - trees[i][2], 2, i});
        edges.push_back({H - trees[i][1] - trees[i][2], 3, i});
        edges.push_back({trees[i][0] - trees[i][2], 4, i});
    }

    sort(ALL(edges));
    memset(ans, 0x3f, sizeof ans);

    //1, 4
    {
        vector<pair<int, int>> ord;
        ord.push_back({1, 4});
        ord.push_back({2, 4});
        ord.push_back({3, 4});
        int l = 0, r = min(W, H);
        while(l < r){
            int m = (l + r + 1) >> 1;
            if(OK(ord, m)){
                l = m;
            } else r = m - 1;
        }
        ans[1][4] = ans[4][1] = l;
    }

    //1, 3
    {
        vector<pair<int, int>> ord;
        ord.push_back({1, 4});
        ord.push_back({1, 3});
        ord.push_back({2, 4});
        ord.push_back({2, 3});
        int l = 0, r = min(W, H);
        while(l < r){
            int m = (l + r + 1) >> 1;
            if(OK(ord, m)){
                l = m;
            } else r = m - 1;
        }
        ans[1][3] = ans[3][1] = l;
    }

    //1, 2
    {
        vector<pair<int, int>> ord;
        ord.push_back({1, 2});
        ord.push_back({1, 3});
        ord.push_back({1, 4});
        int l = 0, r = min(W, H);
        while(l < r){
            int m = (l + r + 1) >> 1;
            if(OK(ord, m)){
                l = m;
            } else r = m - 1;
        }
        ans[1][2] = ans[2][1] = l;
    }

    //2, 4
    {
        vector<pair<int, int>> ord;
        ord.push_back({1, 2});
        ord.push_back({1, 3});
        ord.push_back({2, 4});
        ord.push_back({3, 4});
        int l = 0, r = min(W, H);
        while(l < r){
            int m = (l + r + 1) >> 1;
            if(OK(ord, m)){
                l = m;
            } else r = m - 1;
        }
        ans[2][4] = ans[4][2] = l;
    }

    //2, 3
    {
        vector<pair<int, int>> ord;
        ord.push_back({2, 1});
        ord.push_back({2, 3});
        ord.push_back({2, 4});
        int l = 0, r = min(W, H);
        while(l < r){
            int m = (l + r + 1) >> 1;
            if(OK(ord, m)){
                l = m;
            } else r = m - 1;
        }
        ans[2][3] = ans[3][2] = l;
    }

    //3, 4
    {
        vector<pair<int, int>> ord;
        ord.push_back({3, 1});
        ord.push_back({3, 2});
        ord.push_back({3, 4});
        int l = 0, r = min(W, H);
        while(l < r){
            int m = (l + r + 1) >> 1;
            if(OK(ord, m)){
                l = m;
            } else r = m - 1;
        }
        ans[3][4] = ans[4][3] = l;
    }

//    for(auto o: edges){
//        cout << o[0] << ' ' << o[1] << ' ' << o[2] << '\n';
//    }

//    for(int i = 1; i <= 4; i++){
//        for(int j = i; j <= 4; j++){
//            cout << i << ' ' << j << ' ' << ans[i][j] << '\n';
//        }
//    }

    while(M--){
        int r, c; cin >> r >> c;
        for(int j = 1; j <= 4; j++){
            if(ans[c][j] >= r * 2){
                cout << j;
            }
        }
        cout << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//     freopen("walk.inp","r",stdin);
//     freopen("walk.out","w",stdout);

    int t = 1;
//    cin >> t;
    while(t--)
        solve();

    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 25284 KB Output is correct
2 Correct 266 ms 25148 KB Output is correct
3 Correct 263 ms 25264 KB Output is correct
4 Correct 263 ms 25284 KB Output is correct
5 Correct 272 ms 25276 KB Output is correct
6 Correct 263 ms 25272 KB Output is correct
7 Correct 462 ms 25188 KB Output is correct
8 Correct 461 ms 25200 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2136 KB Output is correct
2 Correct 23 ms 2052 KB Output is correct
3 Correct 21 ms 2132 KB Output is correct
4 Correct 22 ms 2136 KB Output is correct
5 Correct 23 ms 2128 KB Output is correct
6 Correct 27 ms 2128 KB Output is correct
7 Correct 19 ms 1880 KB Output is correct
8 Correct 20 ms 1748 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 25284 KB Output is correct
2 Correct 266 ms 25148 KB Output is correct
3 Correct 263 ms 25264 KB Output is correct
4 Correct 263 ms 25284 KB Output is correct
5 Correct 272 ms 25276 KB Output is correct
6 Correct 263 ms 25272 KB Output is correct
7 Correct 462 ms 25188 KB Output is correct
8 Correct 461 ms 25200 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 24 ms 2136 KB Output is correct
12 Correct 23 ms 2052 KB Output is correct
13 Correct 21 ms 2132 KB Output is correct
14 Correct 22 ms 2136 KB Output is correct
15 Correct 23 ms 2128 KB Output is correct
16 Correct 27 ms 2128 KB Output is correct
17 Correct 19 ms 1880 KB Output is correct
18 Correct 20 ms 1748 KB Output is correct
19 Correct 286 ms 25536 KB Output is correct
20 Correct 273 ms 25424 KB Output is correct
21 Correct 293 ms 25400 KB Output is correct
22 Correct 273 ms 25480 KB Output is correct
23 Correct 281 ms 25476 KB Output is correct
24 Correct 462 ms 25424 KB Output is correct