Submission #339179

#	Time	Username	Problem	Language	Result	Execution time	Memory
339179		12tqian	Park (BOI16_park)	C++17	100 / 100	774 ms	66488 KiB

park

#include <bits/stdc++.h>
using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; i++) 
#define f0r(i, a) f1r(i, 0, a)

#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vpi;

struct DSU {
    std::vector<int> e;
    void init(int n) {
        e = std::vector<int>(n, -1);
    }
    int get(int x) {
        return e[x] < 0 ? x : e[x] = get(e[x]);
    }
    bool same_set(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return -e[get(x)];
    }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) std::swap(x, y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};

ll sq(ll x) {
    return x*x;
}
ld dist(pi x, pi y) {
    return sqrt(sq(x.f-y.f)+sq(x.s-y.s));
}
ld gap(array<int, 3> a, array<int, 3> b) {
    return (dist({a[0], a[1]}, {b[0], b[1]}) - a[2] - b[2])/2;
}
template <class T> bool ckmin(T& x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
ld ti[4][4]; // diameter squared of first time there is a path
struct Edge {
    ld w;
    int u, v;
};
int main() {
    const ll INF = 9e18;
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    int w, h; cin >> w >> h;
    vector<array<int, 3>> trees(n);
    f0r(i, n) 
        cin >> trees[i][0] >> trees[i][1] >> trees[i][2];
    // n, n+1, n+2, n+3
    // 0, 1, 2, 3
    // S, E, N, W
    DSU D; D.init(n+4);
    vector<Edge> ed;
    f0r(i, n) {
        f1r(j, i+1, n) {
            ed.pb({gap(trees[i], trees[j]), i, j});
        }
        ld x = trees[i][0];
        ld y = trees[i][1];
        ld r = trees[i][2];
        ed.pb({(x-r)/2, i, n+3});
        ed.pb({(w-x-r)/2, i, n+1});
        ed.pb({(y-r)/2, i, n});        
        ed.pb({(h-y-r)/2, i, n+2});
    }
    sort(all(ed), [](Edge& e1, Edge& e2) { return e1.w<e2.w; });
    f0r(i, 4) f0r(j, 4) ti[i][j] = INF;
    for (auto& e : ed) {
        ld w = e.w;
        int u = e.u;
        int v = e.v;
        D.unite(u, v);
        f0r(i, 4) {
            f0r(j, 4) {
                if (D.same_set(n+i, n+j)) {
                    ckmin(ti[i][j], w);
                    ckmin(ti[j][i], w);
                }
            }
        }
    }
    f0r(i, m) {
        ll st, r; cin >> r >> st;
        st--;
        vi res;
        f0r(to, 4) {
            if (to == st) {
                res.eb(to);
            } else {
                // st, to-1
                int w1 = st;
                while (w1 != to) {
                    int w2 = to;
                    while (w2 != st) {
                        ld t = ti[w1][w2];
                        if (t < r) {
                            goto fail;
                        }
                        w2++;
                        w2 %= 4;
                    }
                    w1++;
                    w1 %= 4;
                }
                res.eb(to);
                fail: 
                    continue;
            }
        }
        for (auto x : res) cout << x+1;
        cout << '\n';
    }   
}

// 15, 5, 1
// 11 8 1
// 

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