제출 #1158972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158972		nrg_studio	Park (BOI16_park)	C++20	100 / 100	235 ms	26184 KiB

park

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

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector

ll sq(ll x) {return x*x;}

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

    int n, m, w, h; cin >> n >> m >> w >> h;
    v<pair<pii,int>> trees(n);
    v<int> par(n+4), sz(n+4,1);
    iota(all(par),0);
    F0R(i,n) {cin >> trees[i].f.f >> trees[i].f.s >> trees[i].s;}
    v<pair<int,pii>> edges;
    auto dist = [&](int i, int j) {
        return sqrt((double)(sq(trees[i].f.f-trees[j].f.f)+sq(trees[i].f.s-trees[j].f.s)));
    };
    // n: right n+1: top n+2: left n+3: bottom
    F0R(i,n) {
        edges.pb({w-trees[i].f.f-trees[i].s,{i,n}});
        edges.pb({trees[i].f.f-trees[i].s,{i,n+2}});
        edges.pb({trees[i].f.s-trees[i].s,{i,n+3}});
        edges.pb({h-trees[i].f.s-trees[i].s,{i,n+1}});
        FOR(j,i+1,n) {
            edges.pb({dist(i,j)-trees[i].s-trees[j].s,{i,j}});
        }
    }
    sort(all(edges),greater<>());
    v<pair<pii,int>> vis(m);
    F0R(i,m) {cin >> vis[i].f.f >> vis[i].f.s; vis[i].s = i;}
    sort(all(vis));
    v<array<bool,4>> ans(m);

    auto get = [&](auto& get, int x)->int {return par[x]==x ? x : par[x]=get(get,par[x]);};
    auto join = [&](int x, int y) {
        int a = get(get,x), b = get(get,y);
        if (a==b) {return;}
        if (sz[a]<sz[b]) {swap(a,b);}
        par[b] = a; sz[a] += sz[b];
    };
    auto diff = [&](int x, int y) {return get(get,x)!=get(get,y);};

    bool hor = true, ver = true;
    bool tr = true, tl = true, bl = true, br = true;
    F0R(i,m) {
        int idx = vis[i].s, e = --vis[i].f.s;
        while (edges.size() && edges.back().f<2*vis[i].f.f) {
            //cout<<edges.back().f<<'\n';
            //if (idx==0) {
            //    cout<<edges.back().f << ' ' << edges.back().s.f << ' ' << edges.back().s.s << '\n';
            //}

            join(edges.back().s.f,edges.back().s.s);
            edges.pop_back();
        }
        hor &= diff(n,n+2); ver &= diff(n+1,n+3);
        tr &= diff(n,n+1); tl &= diff(n+1,n+2);
        bl &= diff(n+2,n+3); br &= diff(n+3,n);
        F0R(j,4) {ans[idx][j] = true;}

        //if (idx==0) {
        //    cout<<ver<<' ';
        //    cout << edges.size() << '\n';
        //}

        if (e==0) {
            ans[idx][1] &= ver&&br && bl;
            ans[idx][2] &= ver&&hor&&tr && bl;
            ans[idx][3] &= hor&&tl && bl;
        } else if (e==1) {
            ans[idx][2] &= hor&&tr && br;
            ans[idx][3] &= hor&&ver&&tl && br;
            ans[idx][0] &= ver&&bl && br;
        } else if (e==2) {
            ans[idx][3] &= ver&&tl && tr;
            ans[idx][0] &= hor&&ver&&bl && tr;
            ans[idx][1] &= hor&&br && tr;
        } else if (e==3) {
            ans[idx][0] &= hor&&bl && tl;
            ans[idx][1] &= hor&&ver&&br && tl;
            ans[idx][2] &= ver&&tr && tl;
        }
    }
    F0R(i,m) {
        F0R(j,4) {
            if (ans[i][j]) {cout << j+1;}
        } cout << '\n';
    }
    
    /*
    draw edge centers at circles
    get to exit if set of <2r edges does not block off that line segment i.e
    chain of line segments for borders

    store borders as nodes, circles as nodes, connect with dsu in increasing order
    of radii, add edges when necessary
    connect with dsu, check if sides are connected, blah
    */
}

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