제출 #274885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274885		rqi	Park (BOI16_park)	C++14	100 / 100	540 ms	35672 KiB

park

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long double ld;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) begin(x), end(x)

const int MOD = 1000000007;
const int mx = 100005;

int n, m;
ll w, h;
ll k;
ll x[mx];
ll y[mx];
ll r[mx];

ll R[mx];
int e[mx];

pair<vi, vi> sep[7];
pi connec[7];

int his[7]; //lowest value to make it connected

int E[mx];
void init(){
    for(int i = 1; i <= n+4; i++){
        E[i] = -1;
    }
}

int get(int a){
    if(E[a] < 0) return a;
    E[a] = get(E[a]);
    return E[a];
}

void unite(int a, int b){
    a = get(a);
    b = get(b);
    if(a == b) return;
    if(-E[a] < -E[b]) swap(a, b);
    E[a]+=E[b];
    E[b] = a;
}

// int comp[mx];
// vi adj[mx];

// void ae(int a, int b){
//     adj[a].pb(b); adj[b].pb(a);
// }

// void dfs(int node, int val){
//     if(comp[node] != 0) return;
//     comp[node] = val;
//     for(auto u: adj[node]){
//         dfs(u, val);
//     }
// }

// bool works(int ind, ll mid){
//     for(int i = 1; i <= n+4; i++){
//         comp[i] = 0;
//         adj[i].clear();
//     }

//     //add all the edges
//     for(int i = 1; i <= n; i++){
//         for(int j = i+1; j <= n; j++){
//             if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) < (r[i]+r[j]+2*mid)*(r[i]+r[j]+2*mid)){
//                 ae(i, j);
//             }
//         }
//     }

//     for(int i = 1; i <= n; i++){
//         ll xlo = x[i]-r[i]-2*mid;
//         ll xhi = x[i]+r[i]+2*mid;
//         ll ylo = y[i]-r[i]-2*mid;
//         ll yhi = y[i]+r[i]+2*mid;
//         if(xlo < 0){
//             ae(i, n+4);
//         }
//         if(xhi > w){
//             ae(i, n+2);
//         }
//         if(ylo < 0){
//             ae(i, n+1);
//         }
//         if(yhi > h){
//             ae(i, n+3);
//         }
//     }

//     for(int i = 1; i <= n+4; i++){
//         if(comp[i] != 0) continue;
//         dfs(i, i); //node, val
//     }

//     if(comp[connec[ind].f] == comp[connec[ind].s]) return 1;
//     return 0;
// }

// void findHis(){
//     for(int i = 1; i <= 6; i++){
//         ll lo = 0;
//         ll hi = MOD;
//         while(lo < hi){
//             ll mid = (lo+hi)/2;
//             if(works(i, mid)){
//                 hi = mid;
//             }
//             else lo = mid+1;
//         }
//         his[i] = lo;
//     }
// }

ll getSqrt(ll dist2, ll sum){
    if(dist2 == sum*sum) return 1;
    ld dist = sqrt(ld(dist2));
    dist-=ld(sum);
    dist/=ld(2);
    ll res = round(dist);
    while(res >= 1 && dist2 < (sum+2*(res-1))*(sum+2*(res-1))){
        res--;
    }
    while(dist2 >= (sum+2*res)*(sum+2*res)){
        res++;
    }
    return res;
}   

void findHis(){
    vector<pair<ll, pi>> eds;
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            eds.pb(mp(getSqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]), r[i]+r[j]), mp(i, j)));
        }
    }

    for(int i = 1; i <= n; i++){
        ll xlo = x[i]-r[i];
        ll xhi = x[i]+r[i];
        ll ylo = y[i]-r[i];
        ll yhi = y[i]+r[i];
        eds.pb(mp((xlo-0)/2+1, mp(i, n+4)));
        eds.pb(mp((w-xhi)/2+1, mp(i, n+2)));
        eds.pb(mp((ylo-0)/2+1, mp(i, n+1)));
        eds.pb(mp((h-yhi)/2+1, mp(i, n+3)));
    }
    sort(all(eds));



    for(auto u: eds){
        unite(u.s.f, u.s.s);
        //cout << u.f << " " << u.s.f << " " << u.s.s << "\n";
        vi comps(5, 0);
        // for(int i = 1; i <= n+4; i++){
        //     cout << i << " " << E[i] << "\n";
        // }
        for(int j = 1; j <= 4; j++){
            comps[j] = get(n+j);
            //cout << j << " " << comps[j] << "\n";
        }
        for(int j = 1; j <= 6; j++){
            //cout << "HIS " << j << " " << his[j] << "\n";
            if(his[j] != -1) continue;
            if(comps[connec[j].f-n] == comps[connec[j].s-n]){
                his[j] = u.f;
                //cout << "HIS " << j << " " << his[j] << "\n";
            }
        }
    }
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    cin >> w >> h;

    init();

    for(int i = 1; i <= 6; i++){
        his[i] = -1;
    }
    sep[1] = mp(vi{1}, vi{2, 3, 4});
    sep[2] = mp(vi{2}, vi{1, 3, 4});
    sep[3] = mp(vi{3}, vi{1, 2, 4});
    sep[4] = mp(vi{4}, vi{1, 2, 3});
    sep[5] = mp(vi{1, 4}, vi{2, 3});
    sep[6] = mp(vi{1, 2}, vi{3, 4});
    connec[1] = mp(n+1, n+4);
    connec[2] = mp(n+1, n+2);
    connec[3] = mp(n+2, n+3);
    connec[4] = mp(n+3, n+4);
    connec[5] = mp(n+1, n+3);
    connec[6] = mp(n+2, n+4);

    for(int i = 1; i <= n; i++){
        cin >> x[i] >> y[i] >> r[i];
    }
    for(int i = 1; i <= m; i++){
        cin >> R[i] >> e[i];
        k = max(k, r[i]);
    }

    findHis();

    for(int i = 1; i <= m; i++){
        vector<bool> v(5, true);
        for(int j = 1; j <= 6; j++){
            if(R[i] >= his[j]){
                for(auto u: sep[j].f){
                    if(u == e[i]){
                        for(auto z: sep[j].s){
                            v[z] = false;
                        }
                    }
                }
                for(auto u: sep[j].s){
                    if(u == e[i]){
                        for(auto z: sep[j].f){
                            v[z] = false;
                        }
                    }
                }
            }
        }
        for(int j = 1; j <= 4; j++){
            if(v[j] == true) cout << j;
        }
        cout << "\n";
    }
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42