oj.uz

Submission #532172

# Submission time Handle Problem Language Result Execution time Memory
532172 2022-03-02T08:29:19 Z OttoTheDino Park (BOI16_park) C++17
100 / 100
 909 ms 57596 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (ll i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (ll i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const ll mx = 2000;
ll par[mx+5], hh[mx+5];

ll get_par (ll u) {
    if (par[u]==u) return u;
    return get_par(par[u]);
}

void merge (ll u, ll v) {
    ll pu = get_par(u), pv = get_par(v);
    if (hh[pv]>hh[pu]) swap(pu,pv); 
    if (hh[pu]==hh[pv]) ++hh[pu];
    par[pv] = pu;
}

bool con (ll u, ll v) {
    return get_par(u)==get_par(v);
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    ll n, m, w, h; cin >> n >> m >> w >> h;

    rep (i,1,n+4) par[i] = i;

    ll x[n+1], y[n+1], r[n+1];

    rep (i,1,n) cin >> x[i] >> y[i] >> r[i];

    vector<pair<ll,ii>> upds; 

    rep (i,1,n) {
        rep (j,i+1,n) {
            ll lo = 0, hi = 1e9;
            ll d = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
            while (lo<hi) {
                ll mid = (lo+hi)/2, s = 2*mid+r[i]+r[j];
                if (s*s>d) hi = mid;
                else lo = mid+1;
            }
            upds.pb({lo, {i,j}});
        }
        upds.pb({(x[i]-r[i])/2+1, {i,n+1}});
        upds.pb({(y[i]-r[i])/2+1, {i,n+2}});
        upds.pb({(w-x[i]-r[i])/2+1, {i,n+3}});
        upds.pb({(h-y[i]-r[i])/2+1, {i,n+4}});
    }

    sort(all(upds), greater<pair<ll,ii>>());

    vector<pair<ii,int>> queries;

    rep (i,1,m) {
        int R, e; cin >> R >> e;
        queries.pb({{R,e},i});
    }
    string ans[m+1];

    sort(all(queries), greater<pair<ii,int>>());

    rep (k,1,m) {
        int s = queries.back().fi.fi, c = queries.back().fi.se;
        while (upds.size() && s>=upds.back().fi) {
            int u = upds.back().se.fi, v = upds.back().se.se;
            if (!con(u,v)) merge(u,v);
            upds.pop_back();
        }

        bool can[5][5] = {};
        rep (i,1,4) rep (j,1,4) can[i][j] = 1;
        if (con(n+1,n+2)) rep (i,2,4) can[1][i] = can[i][1] = 0;
        if (con(n+2,n+3)) {
            rep (i,1,4) {
                if (i==2) continue;
                can[2][i] = can[i][2] = 0;
            }
        }
        if (con(n+3,n+4)) {
            rep (i,1,4) {
                if (i==3) continue;
                can[3][i] = can[i][3] = 0;
            }
        }
        if (con(n+4,n+1)) {
            rep (i,1,4) {
                if (i==4) continue;
                can[4][i] = can[i][4] = 0;
            }
        }
        if (con(n+4,n+2)) {
            can[4][3] = can[3][4] = 0;
            can[4][2] = can[2][4] = 0;
            can[1][3] = can[3][1] = 0;
            can[1][2] = can[2][1] = 0;
        }
        if (con(n+1,n+3)) {
            can[1][4] = can[4][1] = 0;
            can[1][3] = can[3][1] = 0;
            can[2][4] = can[4][2] = 0;
            can[2][3] = can[3][2] = 0;
        }

        rep (i,1,4) if (can[c][i]) ans[queries.back().se] += to_string(i);
        queries.pop_back();
    }

    rep (i,1,m) cout << ans[i] << "\n";

    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 49792 KB Output is correct
2 Correct 909 ms 49756 KB Output is correct
3 Correct 680 ms 49768 KB Output is correct
4 Correct 668 ms 49788 KB Output is correct
5 Correct 678 ms 49732 KB Output is correct
6 Correct 668 ms 49748 KB Output is correct
7 Correct 638 ms 49788 KB Output is correct
8 Correct 618 ms 49792 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7852 KB Output is correct
2 Correct 63 ms 7736 KB Output is correct
3 Correct 65 ms 7696 KB Output is correct
4 Correct 64 ms 7748 KB Output is correct
5 Correct 57 ms 7756 KB Output is correct
6 Correct 57 ms 7760 KB Output is correct
7 Correct 47 ms 7292 KB Output is correct
8 Correct 53 ms 7348 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 49792 KB Output is correct
2 Correct 909 ms 49756 KB Output is correct
3 Correct 680 ms 49768 KB Output is correct
4 Correct 668 ms 49788 KB Output is correct
5 Correct 678 ms 49732 KB Output is correct
6 Correct 668 ms 49748 KB Output is correct
7 Correct 638 ms 49788 KB Output is correct
8 Correct 618 ms 49792 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 69 ms 7852 KB Output is correct
12 Correct 63 ms 7736 KB Output is correct
13 Correct 65 ms 7696 KB Output is correct
14 Correct 64 ms 7748 KB Output is correct
15 Correct 57 ms 7756 KB Output is correct
16 Correct 57 ms 7760 KB Output is correct
17 Correct 47 ms 7292 KB Output is correct
18 Correct 53 ms 7348 KB Output is correct
19 Correct 736 ms 57396 KB Output is correct
20 Correct 704 ms 57412 KB Output is correct
21 Correct 717 ms 57596 KB Output is correct
22 Correct 768 ms 57280 KB Output is correct
23 Correct 769 ms 57540 KB Output is correct
24 Correct 701 ms 57472 KB Output is correct