oj.uz

Submission #280397

# Submission time Handle Problem Language Result Execution time Memory
280397 2020-08-22T17:18:44 Z caoash Park (BOI16_park) C++14
100 / 100
 991 ms 52920 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((1LL *(x2 - x1) * (x2 - x1)) + (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;
        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) {
        while (p < sz(qrs) && qrs[p].f.f <= v.f){
            bool conn[4][4];
            pair<pi, int> curr = qrs[p];
            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];
                }
            }
            auto bad = [&] (const int &x) {
                return conn[(x - 1 < 0 ? 3 : x - 1)][x];
            };
            for (int i = 0; i < 4; i++) {
                if (curr.f.s == i) {
                    continue;
                }
                if (bad(curr.f.s) || bad(i)) {
                    ok[curr.s][i] = false;
                    continue;
                }
                bool upok = conn[0][2];
                bool sok = conn[1][3];
                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;
        }
        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 909 ms 50412 KB Output is correct
2 Correct 946 ms 50436 KB Output is correct
3 Correct 941 ms 50412 KB Output is correct
4 Correct 934 ms 50412 KB Output is correct
5 Correct 904 ms 50436 KB Output is correct
6 Correct 885 ms 50412 KB Output is correct
7 Correct 776 ms 50156 KB Output is correct
8 Correct 779 ms 50156 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 81 ms 4036 KB Output is correct
2 Correct 77 ms 4036 KB Output is correct
3 Correct 76 ms 4044 KB Output is correct
4 Correct 76 ms 4040 KB Output is correct
5 Correct 77 ms 4040 KB Output is correct
6 Correct 81 ms 4044 KB Output is correct
7 Correct 68 ms 3560 KB Output is correct
8 Correct 67 ms 3560 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 50412 KB Output is correct
2 Correct 946 ms 50436 KB Output is correct
3 Correct 941 ms 50412 KB Output is correct
4 Correct 934 ms 50412 KB Output is correct
5 Correct 904 ms 50436 KB Output is correct
6 Correct 885 ms 50412 KB Output is correct
7 Correct 776 ms 50156 KB Output is correct
8 Correct 779 ms 50156 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 81 ms 4036 KB Output is correct
12 Correct 77 ms 4036 KB Output is correct
13 Correct 76 ms 4044 KB Output is correct
14 Correct 76 ms 4040 KB Output is correct
15 Correct 77 ms 4040 KB Output is correct
16 Correct 81 ms 4044 KB Output is correct
17 Correct 68 ms 3560 KB Output is correct
18 Correct 67 ms 3560 KB Output is correct
19 Correct 991 ms 52908 KB Output is correct
20 Correct 948 ms 52836 KB Output is correct
21 Correct 964 ms 52792 KB Output is correct
22 Correct 944 ms 52844 KB Output is correct
23 Correct 952 ms 52920 KB Output is correct
24 Correct 850 ms 52664 KB Output is correct