Submission #274877

#	Time	Username	Problem	Language	Result	Execution time	Memory
274877		rqi	Park (BOI16_park)	C++14	31 / 100	2564 ms	19888 KiB

park

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

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

#define mp make_pair
#define f first
#define s second
#define pb push_back

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 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;
    }
}

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

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