oj.uz

Submission #877836

# Submission time Handle Problem Language Result Execution time Memory
877836 2023-11-23T17:31:23 Z Hamed_Ghaffari Park (BOI16_park) C++17
100 / 100
 506 ms 68284 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll
#define double long double

typedef long long       ll;
typedef pair<int, int>  pii;

#define FastIO          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define FileIO          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define F               first
#define S               second
#define max_heap(T)     priority_queue<T>
#define min_heap(T)     priority_queue<T, vector<T>, greater<T>>
#define fr(i,a,b)       for(int i=a;i<b;i++)
#define frr(i,a,b)      for(int i=a;i>b;i--)
#define frin(i,A)       for(auto &i : A)
#define frp(a,b,A)      for(auto [a, b] : A)
#define SZ(x)           (int)x.size()
#define all(A)          A.begin(), A.end()
#define mins(a,b)       a = min(a,b)
#define maxs(a,b)       a = max(a,b)
#define pb              push_back
#define kill(x)         cout << x << '\n', exit(0)
#define md(a)           (a%MOD+MOD)%MOD

const ll  INF  = 4e18;
const ll  MOD  = 1e9 + 7;
const int MAXN = 2008;
const int LOG  = 30;

double dis(pii p1, pii p2) {
    double x = p1.F-p2.F, y = p1.S-p2.S;
    return sqrt(x*x + y*y);
}

int w, h, n, m;
struct circle { int x, y, r; } C[MAXN];
struct edge { 
    int u, v;
    double w;
    edge() {}
    edge(int u_, int v_, double w_) {
        u = u_, v = v_, w = w_;
    }
    bool operator < (const edge &e) const {
        return w < e.w;
    }
};
vector<edge> E;
struct DSU {
    int par[MAXN], sz[MAXN];
    void clear() {
        fr(i, 0, MAXN)
            par[i] = i,
            sz[i] = 1;
    }
    int Find(int v) {
        return v == par[v] ? v : par[v] = Find(par[v]);
    }
    bool Union(int u, int v) {
        if((u = Find(u)) == (v = Find(v)))
            return 0;
        if(sz[u] < sz[v])
            swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return 1;
    }
} dsu;
double fir[5][5];

void solve() {
    cin >> n >> m;
    cin >> w >> h;
    fr(i, 1, n+1) {
        cin >> C[i].x >> C[i].y >> C[i].r;
        E.pb({i, n+1, 1.0*(h-(C[i].y+C[i].r))});
        E.pb({i, n+2, 1.0*(w-(C[i].x+C[i].r))});
        E.pb({i, n+3, 1.0*(C[i].y-C[i].r)});
        E.pb({i, n+4, 1.0*(C[i].x-C[i].r)});
    }
    fr(i, 1, n+1)
        fr(j, i+1, n+1)
            E.pb({i, j, dis({C[i].x, C[i].y}, {C[j].x, C[j].y})-C[i].r-C[j].r});
    sort(all(E));
    dsu.clear();
    fr(i, 1, 5)
        fr(j, 1, 5)
            fir[i][j] = INF;
    frin(e, E) {
        dsu.Union(e.u, e.v);
        fr(i, 1, 5)
            fr(j, 1, 5)
                if(i != j && dsu.Find(n+i) == dsu.Find(n+j))
                    mins(fir[i][j], e.w);
    }
    while(m--) {
        ll r;
        int e;
        cin >> r >> e;
        r *= 2;
        if(e == 1) {
            cout << 1;
            if(min({fir[1][3], fir[2][3], fir[3][4]}) >= r) cout << 2;
            if(min({fir[1][3], fir[2][4], fir[3][4], fir[1][2]}) >= r) cout << 3;
            if(min({fir[2][4], fir[1][4], fir[3][4]}) >= r) cout << 4;
        }
        if(e == 2) {
            if(min({fir[1][3], fir[2][3], fir[3][4]}) >= r) cout << 1;
            cout << 2;
            if(min({fir[2][4], fir[1][2], fir[2][3]}) >= r) cout << 3;
            if(min({fir[1][3], fir[2][4], fir[2][3], fir[1][4]}) >= r) cout << 4;
        }
        if(e == 3) {
            if(min({fir[1][3], fir[2][4], fir[3][4], fir[1][2]}) >= r) cout << 1;
            if(min({fir[2][4], fir[1][2], fir[2][3]}) >= r) cout << 2;
            cout << 3;
            if(min({fir[1][2], fir[1][4], fir[1][3]}) >= r) cout << 4;
        }
        if(e == 4) {
            if(min({fir[2][4], fir[1][4], fir[3][4]}) >= r) cout << 1;
            if(min({fir[1][3], fir[2][4], fir[2][3], fir[1][4]}) >= r) cout << 2;
            if(min({fir[1][2], fir[1][4], fir[1][3]}) >= r) cout << 3;
            cout << 4;
        }
        cout << '\n';
    }
}

int32_t main() {
    FastIO
    int T = 1;
    // cin >> T;
    while(T--)
        solve();
    return 0;
}

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 68244 KB Output is correct
2 Correct 464 ms 67532 KB Output is correct
3 Correct 467 ms 67500 KB Output is correct
4 Correct 476 ms 67752 KB Output is correct
5 Correct 466 ms 67012 KB Output is correct
6 Correct 468 ms 68268 KB Output is correct
7 Correct 380 ms 66984 KB Output is correct
8 Correct 406 ms 66548 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1584 KB Output is correct
2 Correct 29 ms 2560 KB Output is correct
3 Correct 29 ms 2428 KB Output is correct
4 Correct 29 ms 2508 KB Output is correct
5 Correct 29 ms 2520 KB Output is correct
6 Correct 30 ms 2500 KB Output is correct
7 Correct 25 ms 1884 KB Output is correct
8 Correct 24 ms 1872 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 68244 KB Output is correct
2 Correct 464 ms 67532 KB Output is correct
3 Correct 467 ms 67500 KB Output is correct
4 Correct 476 ms 67752 KB Output is correct
5 Correct 466 ms 67012 KB Output is correct
6 Correct 468 ms 68268 KB Output is correct
7 Correct 380 ms 66984 KB Output is correct
8 Correct 406 ms 66548 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 30 ms 1584 KB Output is correct
12 Correct 29 ms 2560 KB Output is correct
13 Correct 29 ms 2428 KB Output is correct
14 Correct 29 ms 2508 KB Output is correct
15 Correct 29 ms 2520 KB Output is correct
16 Correct 30 ms 2500 KB Output is correct
17 Correct 25 ms 1884 KB Output is correct
18 Correct 24 ms 1872 KB Output is correct
19 Correct 492 ms 68160 KB Output is correct
20 Correct 497 ms 68284 KB Output is correct
21 Correct 506 ms 68008 KB Output is correct
22 Correct 489 ms 66584 KB Output is correct
23 Correct 488 ms 68284 KB Output is correct
24 Correct 417 ms 66984 KB Output is correct