Submission #1096359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096359		TrinhKhanhDung	Park (BOI16_park)	C++14	100 / 100	462 ms	25536 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42