oj.uz

Submission #265587

# Submission time Handle Problem Language Result Execution time Memory
265587 2020-08-15T02:20:16 Z caoash Park (BOI16_park) C++14
100 / 100
 1110 ms 52968 KB 
#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 = 2006;

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> dsu; bool ok[100005][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 int &x1, const int &y1, const int &x2, const int &y2) {
        return sqrt((ll)(1LL *(x2 - x1) * (ll)(x2 - x1)) + (ll)(1LL * (y2 - y1) * (y2 - y1)));
    };
    auto add = [&] (const int &x1, const int &y1, const int &x2, const int &y2, const ll &r1, const ll &r2) {
        ll ndist = dist(x1, y1, x2, y2) - r1 - r2;
        // cout << "adding: " << x1 << " " << y1 << " " << x2 << " " << y2 << " " << ndist << endl; 
        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++;
    }
    assert(cnt <= n + 4);
    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';
        // cout << cc[v.s.f] << " " << cc[v.s.s] << endl;
        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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 50412 KB Output is correct
2 Correct 929 ms 50436 KB Output is correct
3 Correct 876 ms 50564 KB Output is correct
4 Correct 899 ms 50412 KB Output is correct
5 Correct 890 ms 50436 KB Output is correct
6 Correct 881 ms 50412 KB Output is correct
7 Correct 774 ms 50160 KB Output is correct
8 Correct 790 ms 50180 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 3016 KB Output is correct
2 Correct 80 ms 4040 KB Output is correct
3 Correct 80 ms 4076 KB Output is correct
4 Correct 76 ms 4040 KB Output is correct
5 Correct 78 ms 4040 KB Output is correct
6 Correct 84 ms 4044 KB Output is correct
7 Correct 71 ms 3560 KB Output is correct
8 Correct 68 ms 3516 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 50412 KB Output is correct
2 Correct 929 ms 50436 KB Output is correct
3 Correct 876 ms 50564 KB Output is correct
4 Correct 899 ms 50412 KB Output is correct
5 Correct 890 ms 50436 KB Output is correct
6 Correct 881 ms 50412 KB Output is correct
7 Correct 774 ms 50160 KB Output is correct
8 Correct 790 ms 50180 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 85 ms 3016 KB Output is correct
12 Correct 80 ms 4040 KB Output is correct
13 Correct 80 ms 4076 KB Output is correct
14 Correct 76 ms 4040 KB Output is correct
15 Correct 78 ms 4040 KB Output is correct
16 Correct 84 ms 4044 KB Output is correct
17 Correct 71 ms 3560 KB Output is correct
18 Correct 68 ms 3516 KB Output is correct
19 Correct 1110 ms 52968 KB Output is correct
20 Correct 966 ms 52924 KB Output is correct
21 Correct 962 ms 52856 KB Output is correct
22 Correct 947 ms 52664 KB Output is correct
23 Correct 974 ms 52796 KB Output is correct
24 Correct 863 ms 52664 KB Output is correct