oj.uz

Submission #723913

# Submission time Handle Problem Language Result Execution time Memory
723913 2023-04-14T12:50:04 Z nicky4321 Park (BOI16_park) C++17
100 / 100
 2344 ms 162004 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
ll x[MAX], y[MAX], r[MAX], ptr[MAX], num[MAX];
vector<pair<ll, pii> > qq;
string ans[MAX];

int find(int x){
    return x != ptr[x] ? ptr[x] = find(ptr[x]) : x;
}

void uf(int u, int v){
    u = find(u);
    v = find(v);
    if(u == v)
        return;
    if(num[u] > num[v])
        swap(u, v);
    num[v] += num[u];
    ptr[u] = v;
    return;
}

void solve(){
    int n, q;
    cin >> n >> q;
    ll w, h;
    cin >> w >> h;
    for(int i = 1;i <= n;i++){
        cin >> x[i] >> y[i] >> r[i];
    }
    for(int i = 1;i <= q;i++){
        ll rr, ty;
        cin >> rr >> ty;
        qq.PB(MP(rr, MP(ty, i)));
    }
    sort(ALL(qq));
    for(int i = 1;i <= n + 4;i++){
        ptr[i] = i;
        num[i] = 1;
    }
    set<pair<ll, pii> > st;
    for(int i = 1;i <= n;i++){
        for(int j = i + 1;j <= n;j++){
            ll tmp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
            st.insert(MP(ceil(sqrt(tmp)) - r[i] - r[j] + (ceil(sqrt(tmp)) * ceil(sqrt(tmp)) == tmp), MP(i, j)));
        }
    }
    for(int i = 1;i <= n;i++){
        st.insert(MP(x[i] - r[i] + 1, MP(i, n + 1)));
        st.insert(MP(h - y[i] - r[i] + 1, MP(i, n + 2)));
        st.insert(MP(w - x[i] - r[i] + 1, MP(i, n + 3)));
        st.insert(MP(y[i] - r[i] + 1, MP(i, n + 4)));
    }
    for(int i = 0;i < q;i++){
        ll rr = qq[i].F, ty = qq[i].S.F, id = qq[i].S.S;
        while(!st.empty() && (*st.begin()).F <= rr * 2){
            uf((*st.begin()).S.F, (*st.begin()).S.S);
            st.erase(st.begin());
        }
        if(ty == 1){
            ans[id] += "1";
            if(find(n + 4) != find(n + 1) && find(n + 4) != find(n + 2) && find(n + 4) != find(n + 3))
                ans[id] += "2";
            if(find(n + 2) != find(n + 4) && find(n + 2) != find(n + 3) && find(n + 1) != find(n + 4) && find(n + 1) != find(n + 3))
                ans[id] += "3";
            if(find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3) && find(n + 1) != find(n + 4))
                ans[id] += "4";
        }else if(ty == 2){
            if(find(n + 4) != find(n + 1) && find(n + 4) != find(n + 2) && find(n + 4) != find(n + 3))
                ans[id] += "1";
            ans[id] += "2";
            if(find(n + 3) != find(n + 1) && find(n + 3) != find(n + 2) && find(n + 3) != find(n + 4))
                ans[id] += "3";
            if(find(n + 2) != find(n + 4) && find(n + 3) != find(n + 4) && find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3))
                ans[id] += "4";
        }else if(ty == 3){
            if(find(n + 2) != find(n + 4) && find(n + 2) != find(n + 3) && find(n + 1) != find(n + 4) && find(n + 1) != find(n + 3))
                ans[id] += "1";
            if(find(n + 3) != find(n + 1) && find(n + 3) != find(n + 2) && find(n + 3) != find(n + 4))
                ans[id] += "2";
            ans[id] += "3";
            if(find(n + 2) != find(n + 1) && find(n + 2) != find(n + 3) && find(n + 2) != find(n + 4))
                ans[id] += "4";
        }else{
            if(find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3) && find(n + 1) != find(n + 4))
                ans[id] += "1";
            if(find(n + 2) != find(n + 4) && find(n + 3) != find(n + 4) && find(n + 1) != find(n + 2) && find(n + 1) != find(n + 3))
                ans[id] += "2";
            if(find(n + 2) != find(n + 1) && find(n + 2) != find(n + 3) && find(n + 2) != find(n + 4))
                ans[id] += "3";
            ans[id] += "4";
        }
    }
    for(int i = 1;i <= q;i++)
        cout << ans[i] << '\n';
}
/*
 2
1 3
 4
*/
int main(){
    IOS
    // CASE
        solve();
    return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2 
10 4 1
15 5 1
1 1
2 2
2 1
*/

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2166 ms 159088 KB Output is correct
2 Correct 2220 ms 158968 KB Output is correct
3 Correct 2184 ms 159052 KB Output is correct
4 Correct 2139 ms 159028 KB Output is correct
5 Correct 2251 ms 158880 KB Output is correct
6 Correct 2320 ms 158940 KB Output is correct
7 Correct 1917 ms 158984 KB Output is correct
8 Correct 1884 ms 158976 KB Output is correct
9 Correct 17 ms 33196 KB Output is correct
10 Correct 17 ms 33160 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 37420 KB Output is correct
2 Correct 63 ms 37332 KB Output is correct
3 Correct 64 ms 37316 KB Output is correct
4 Correct 68 ms 37360 KB Output is correct
5 Correct 70 ms 37396 KB Output is correct
6 Correct 64 ms 37488 KB Output is correct
7 Correct 58 ms 36308 KB Output is correct
8 Correct 57 ms 36260 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2166 ms 159088 KB Output is correct
2 Correct 2220 ms 158968 KB Output is correct
3 Correct 2184 ms 159052 KB Output is correct
4 Correct 2139 ms 159028 KB Output is correct
5 Correct 2251 ms 158880 KB Output is correct
6 Correct 2320 ms 158940 KB Output is correct
7 Correct 1917 ms 158984 KB Output is correct
8 Correct 1884 ms 158976 KB Output is correct
9 Correct 17 ms 33196 KB Output is correct
10 Correct 17 ms 33160 KB Output is correct
11 Correct 63 ms 37420 KB Output is correct
12 Correct 63 ms 37332 KB Output is correct
13 Correct 64 ms 37316 KB Output is correct
14 Correct 68 ms 37360 KB Output is correct
15 Correct 70 ms 37396 KB Output is correct
16 Correct 64 ms 37488 KB Output is correct
17 Correct 58 ms 36308 KB Output is correct
18 Correct 57 ms 36260 KB Output is correct
19 Correct 2344 ms 161960 KB Output is correct
20 Correct 2131 ms 161848 KB Output is correct
21 Correct 2264 ms 161840 KB Output is correct
22 Correct 2278 ms 161828 KB Output is correct
23 Correct 2242 ms 162004 KB Output is correct
24 Correct 1823 ms 161912 KB Output is correct