Submission #265573

#	Time	Username	Problem	Language	Result	Execution time	Memory
265573		caoash	Park (BOI16_park)	C++14	27 / 100	914 ms	79804 KiB

park

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

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const int MX = 2005;

vector<pair<ll, pair<pi, pi>>> ed; map<pi, int> cc;

template<int SZ> struct DSU{
    int p[SZ], sz[SZ];
    void init(){
        for(int i = 0; i < SZ; i++){
            p[i] = i; sz[i] = 1;
        }
    }
    int find(int x){
        return p[x] = (p[x] == x ? x : find(p[x]));
    }
    void merge(int u, int v){
        int a = find(u); int b = find(v);
        if(a != b){
            if(sz[a] < sz[b]){
                swap(a,b);
            }
            p[b] = a;
            sz[a] += sz[b];
        }
    }
};

DSU<MX * MX> dsu; bool ok[2005][4];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, w, h; cin >> n >> m >> w >> h;
    vector<pair<pair<ll, ll>, int>> trees(n);
    set<pi> pts;
    auto dist = [&] (const ll &x1, const ll &y1, const ll &x2, const ll &y2) {
        return floor(sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)));
    };
    auto add = [&] (const ll &x1, const ll &y1, const ll &x2, const ll &y2, const ll &r1, const ll &r2) {
        ll ndist = dist(x1, y1, x2, y2) - r1 - r2;
        // cout << "adding: " << x1 << " " << y1 << " " << x2 << " " << y2 << " " << ndist << '\n'; 
        ed.pb(mp(ndist, mp(mp(x1, y1), mp(x2, y2))));
    };
    for (int i = 0; i < n; i++) {
        cin >> trees[i].f.f >> trees[i].f.s >> trees[i].s;
        pts.insert(mp(trees[i].f.f, trees[i].f.s));
        cc[mp(0, trees[i].f.s)] = 3;
        cc[mp(trees[i].f.f, h)] = 2;
        cc[mp(w, trees[i].f.s)] = 1;
        cc[mp(trees[i].f.f, 0)] = 0;
        add(trees[i].f.f, trees[i].f.s, 0, trees[i].f.s, trees[i].s, 0);
        add(trees[i].f.f, trees[i].f.s, trees[i].f.f, 0, trees[i].s, 0);
        add(trees[i].f.f, trees[i].f.s, w, trees[i].f.s, trees[i].s, 0);
        add(trees[i].f.f, trees[i].f.s, trees[i].f.f, h, trees[i].s, 0);
    }
    int cnt = 4;
    for (pi x : pts) {
        cc[x] = cnt++;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            add(trees[i].f.f, trees[i].f.s, trees[j].f.f, trees[j].f.s, trees[i].s, trees[j].s);
        }
    }
    vector<pair<pi, int>> qrs;
    for (int i = 0; i < m; i++) {
        int r, e; cin >> r >> e;
        e--;
        qrs.pb(mp(mp(2 * r, e), i));
    }
    sort(all(qrs));
    sort(all(ed));
    dsu.init();
    int p = 0;
    memset(ok, true, sizeof(ok));
    for (auto v : ed) {
        // cout << "ed: " << v.f << "\n";
        while (p < sz(qrs) && qrs[p].f.f <= v.f){
            bool conn[4][4];
            pair<pi, int> curr = qrs[p];
            // cout << "qry: " << curr.f.f << " " << curr.f.s << " " << '\n';
            for (int i = 0; i < 4; i++) {
                conn[i][i] = true;
                for (int j = i + 1; j < 4; j++) {
                    conn[i][j] = (dsu.find(i) == dsu.find(j));
                    conn[j][i] = conn[i][j];
                    // cout << "i j conn " << i << " " << j << " " << conn[i][j] << '\n';
                }
            }
            auto bad = [&] (const int &x) {
                // if(conn[(x - 1 < 0 ? 3 : x - 1)][x]) cout << "BAD: " << x << '\n';
                return conn[(x - 1 < 0 ? 3 : x - 1)][x];
            };
            for (int i = 0; i < 4; i++) {
                if (curr.f.s == i) {
                    continue;
                }
                // cout << curr.f.s << " " << i << " " << bad(curr.f.s) << " " << bad(i) << '\n';
                if (bad(curr.f.s) || bad(i)) {
                    ok[curr.s][i] = false;
                    continue;
                }
                bool upok = conn[0][2];
                bool sok = conn[1][3];
                // cout << "i, curr.f.s, upok, sok: " << i << " " << curr.f.s << " " << upok << " " << sok << '\n';
                if (abs(curr.f.s - i) == 2) {
                    if (upok || sok) {
                        ok[curr.s][i] = false;
                        continue;
                    }
                }
                else if(curr.f.s + i == 3) {
                    if (sok) {
                        ok[curr.s][i] = false;
                        continue;
                    }
                }
                else {
                    if (upok) {
                        ok[curr.s][i] = false; 
                    }
                }
            }
            ++p;
            if (p >= sz(qrs)) break;
        }
        // cout << "merging: " << v.s.f.f << " " << v.s.f.s << " " << v.s.s.f << " " << v.s.s.s << '\n';
        // cout << "merging: " << cc[v.s.f] << " " << cc[v.s.s] << '\n';
        dsu.merge(cc[v.s.f], cc[v.s.s]);
    }
    for (int i = 0; i < m; i++) {
        string ret = "";
        for (int j = 0; j < 4; j++) {
            if (ok[i][j]) ret += to_string(j + 1);
        }
        cout << ret << '\n';
    }
}

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