제출 #723913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723913		nicky4321	Park (BOI16_park)	C++17	100 / 100	2344 ms	162004 KiB

park

#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 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42