Submission #485796

#	Time	Username	Problem	Language	Result	Execution time	Memory
485796		radal	Park (BOI16_park)	C++14	100 / 100	451 ms	67380 KiB

park

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<long double,long double> pld;
const long long int N = 2e3+10,mod = 1e9+7,inf = 1e9,sq = 500,maxm = 1e5+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,ll k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
vector<pair<long double,pll> > e;
pair<pll,int> point[N];
int par[N];
inline ld dist(pll a,pll b){
    return sqrt(ld((a.X-b.X)*(a.X-b.X)+(a.Y-b.Y)*(a.Y-b.Y)));
}
inline ld dist(pair<pll,int> p1,pair<pll,int> p2){
    return dist(p1.X,p2.X)-p1.Y-p2.Y;
}
int getpar(int v){
    if (par[v] == v) return v;
    return par[v] = getpar(par[v]);
}
inline void mg(int u,int v){
    u = getpar(u);
    v = getpar(v);
    par[u] = v;
    return;
}
pair<pll,int> a[maxm];
bool ans[maxm][4];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m,w,h;
    cin >> n >> m >> w >> h;
    e.reserve(n*n+6*n);
    rep(i,1,n+1){
        par[i] = i;
        cin >> point[i].X.X >> point[i].X.Y >> point[i].Y;
        rep(j,1,i){
            e.pb({dist(point[i],point[j]),{i,j}});
        }
    }
    rep(i,1,5) par[n+i] = n+i;
    rep(i,1,n+1){
        int x = point[i].X.X,y = point[i].X.Y,r = point[i].Y;
        e.pb({y-r,{n+1,i}});
        e.pb({x-r,{n+4,i}});
        e.pb({w-x-r,{n+2,i}});
        e.pb({h-y-r,{n+3,i}});
    }
    rep(i,0,m){
        cin >> a[i].X.X >> a[i].X.Y;
        a[i].Y = i;
        a[i].X.X *= 2;
        a[i].X.Y--;
    }
    sort(e.begin(),e.end());
    sort(a,a+m);
    int l = -1;
    int sz = e.size();
    rep(i,0,m){
        while (l < sz-1 && e[l+1].X < a[i].X.X){
            l++;
            mg(e[l].Y.X,e[l].Y.Y);
        }
        int st = a[i].X.Y,ind = a[i].Y;
        ans[ind][st] = 1;
        int u1=  getpar(n+1),u2 = getpar(n+2),u3 = getpar(n+3),u4 = getpar(n+4);
        if (st == 0){
            if (u1 != u2 && u1 != u3 && u1 != u4) ans[ind][1] = 1;
            if (u1 != u3 && u2 != u4 && u1 != u4 && u2 != u3) ans[ind][2] = 1;
            if (u4 != u2 && u4 != u3 && u1 != u4) ans[ind][3] = 1;
        }
        if (st == 1){
            if (u1 != u2 && u1 != u3 && u1 != u4) ans[ind][0] = 1;
            if (u1 != u2 && u2 != u4 && u2 != u3) ans[ind][2] = 1;
            if (u4 != u2 && u4 != u3 && u1 != u2 && u1 != u3) ans[ind][3] = 1;
        }
        if (st == 2){
            if (u1 != u2 && u2 != u3 && u2 != u4) ans[ind][1] = 1;
            if (u1 != u3 && u2 != u4 && u1 != u4 && u2 != u3) ans[ind][0] = 1;
            if (u3 != u2 && u4 != u3 && u1 != u3) ans[ind][3] = 1;
        }
        if (st == 3){
            if (u4 != u2 && u4 != u3 && u1 != u4) ans[ind][0] = 1;
            if (u1 != u3 && u2 != u4 && u1 != u2 && u4 != u3) ans[ind][1] = 1;
            if (u3 != u2 && u4 != u3 && u3 != u4) ans[ind][2] = 1;
        }
    }
    rep(i,0,m){
        rep(j,0,4) if (ans[i][j]) cout << j+1;
        cout << endl;
    }
}

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