Submission #1275184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275184		garam1732	Park (BOI16_park)	C++20	100 / 100	819 ms	23228 KiB

park

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*2;
const ll MOD = 998244353;
const ll INF = 2e9;

int par[2020];
int root(int x){return par[x]==x?x:par[x]=root(par[x]);}
void merge(int a, int b) {
    a=root(a), b=root(b);
    if(a^b) par[a]=b;
}

struct Circle {
    int x,y,r;
} arr[2020];

struct Visitor {
    int r,c,x;
} qry[100100];

vector<pi> v;
int U, D, L, R;
int n, m;
int w, h;

ll dist(pi a, pi b) {
    return (ll)(a.ff-b.ff)*(a.ff-b.ff) + (ll)(a.ss-b.ss)*(a.ss-b.ss);
}

double f(pi a) {
    int p=a.ff, q=a.ss;
    if(q < n) {
        return sqrt((double)dist(pi(arr[p].x,arr[p].y), pi(arr[q].x,arr[q].y))) - arr[p].r - arr[q].r;
    }

    if(q == U) return (h-arr[p].y-arr[p].r);
    if(q == D) return (arr[p].y-arr[p].r);
    if(q == R) return (w-arr[p].x-arr[p].r);
    return (arr[p].x-arr[p].r);
}

bool cmp(pi a, pi b) {
    return f(a) < f(b);
}

vector<int> res[100100];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>m; cin>>w>>h;
    for(int i=0;i<n;i++) {
        cin>>arr[i].x>>arr[i].y>>arr[i].r;
    }

    U=n, D=n+1, L=n+2, R=n+3;
    for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) v.push_back({i,j});
    for(int i=0;i<n;i++) for(int j=n;j<n+4;j++) v.push_back({i,j});
    sort(all(v), cmp);

    for(int i=0;i<n+4;i++) par[i]=i;

    for(int i=0;i<m;i++) {
        cin>>qry[i].r>>qry[i].c; qry[i].x=i;
    } sort(qry, qry+m, [&](Visitor &a, Visitor &b){return a.r<b.r;});

    for(int i=0, idx=0;i<m;i++) {
        while(idx<v.size() && f(v[idx]) < 2*qry[i].r) {
            merge(v[idx].ff, v[idx].ss);
            idx++;
        }

        bool chk[5] = {1,1,1,1,1};
        if((root(D) == root(L))) {
            if(qry[i].c == 1) {for(int x:{1,2,3,4}) if(x^1) chk[x]=0;}
            else chk[1]=0;
        } if((root(D) == root(R))) {
            if(qry[i].c == 2) {for(int x:{1,2,3,4}) if(x^2) chk[x]=0;}
            else chk[2]=0;
        } if((root(U) == root(R))) {
            if(qry[i].c == 3) {for(int x:{1,2,3,4}) if(x^3) chk[x]=0;}
            else chk[3]=0;
        } if((root(U) == root(L))) {
            if(qry[i].c == 4) {for(int x:{1,2,3,4}) if(x^4) chk[x]=0;}
            else chk[4]=0;
        }

        if(root(U) == root(D)) {
            if(qry[i].c == 1 || qry[i].c == 4) chk[2] = chk[3] = 0;
            else chk[1] = chk[4] = 0;
        } if(root(L) == root(R)) {
            if(qry[i].c == 1 || qry[i].c == 2) chk[3] = chk[4] = 0;
            else chk[1] = chk[2] = 0;
        }
        
        for(int x:{1,2,3,4}) if(chk[x]) res[qry[i].x].push_back(x);
    } for(int i=0;i<m;i++) {
        for(int x:res[i]) cout<<x;cout<<endl;
    }
}

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