제출 #1310555

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310555		edo	Park (BOI16_park)	C++20	100 / 100	244 ms	36156 KiB

park

#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;
using i128 = __int128_t;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }
template<typename T> T maxel(const vector<T>& v){ return *max_element(v.begin(), v.end()); }
template<typename T> T minel(const vector<T>& v){ return *min_element(v.begin(), v.end()); }
template<typename T, int N> T maxel(T (&a)[N]) { return *max_element(a, a + N); }
template<typename T, int N> T minel(T (&a)[N]) { return *min_element(a, a + N); }


template<typename C, typename T> auto lb(C& c, const T& x){ return std::lower_bound(c.begin(), c.end(), x); }
template<typename C, typename T> auto ub(C& c, const T& x){ return std::upper_bound(c.begin(), c.end(), x); }

template<typename T> auto lb(std::set<T>& s, const T& x){ return s.lower_bound(x); }
template<typename T> auto ub(std::set<T>& s, const T& x){ return s.upper_bound(x); }
template<typename T> auto lb(const std::set<T>& s, const T& x){ return s.lower_bound(x); }
template<typename T> auto ub(const std::set<T>& s, const T& x){ return s.upper_bound(x); }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")

struct DSU {
    int n;
    std::vector<int> parent_or_size;

    DSU() : n(0) {}
    DSU(int n) : n(n), parent_or_size(n, -1) {}

    int leader(int a) {
        return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]);
    }

    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

    int size(int a) {
        return -parent_or_size[leader(a)];
    }

    int merge(int a, int b) {
        a = leader(a), b = leader(b);
        if (a == b) return a;
        if (-parent_or_size[a] < -parent_or_size[b]) std::swap(a, b);
        parent_or_size[a] += parent_or_size[b];
        parent_or_size[b] = a;
        return a;
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(n), group_size(n);
        for (int i = 0; i < n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(n);
        for (int i = 0; i < n; i++) result[i].reserve(group_size[i]);
        for (int i = 0; i < n; i++) result[leader_buf[i]].push_back(i);
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }
}dsu;

struct S {
    int x, y;
    ll r;
    bool operator<(S& other) {
        return r < other.r;
    }
};

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, w, h;
    sc(n, m, w, h);

    vc<S> tree, ppl;
    const int nax = 2020;
    int x[nax], y[nax], r[nax];

    FOR(i, 5, n + 5) {
        sc(x[i], y[i], r[i]);
        FOR(j, 5, i) {
            ll c = floor(hypot(x[i] - x[j], y[i] - y[j])) + 1 - r[i] - r[j];
            tree.pb({i, j, c});
        }
        tree.pb({i, 1, y[i] - r[i] + 1});
        tree.pb({i, 2, w - x[i] - r[i] + 1});
        tree.pb({i, 3, h - y[i] - r[i] + 1});
        tree.pb({i, 4, x[i] - r[i] + 1});
    }
    tree.pb({1, 1, (ll)1e18});
    int F = (1 << 4) - 1;
    vi ans(m + 5, F);
    FOR(m) {
        S t;
        sc(t.r, t.y);
        t.r <<= 1;
        t.x = i + 1;
        ppl.pb(t);
    }

    sort(all(ppl)); sort(all(tree));
    
    const int C1[] = {1, 1, 1, 2, 2, 3};
    const int C2[] = {2, 3, 4, 3, 4, 4};
    const int MS[] = {2, 6, 1, 4, 3, 7};

    auto mask = [&](int X, int ul) {
        return ((1 << (ul - 1)) & X) ? X : X ^ F;
    };
    
    dsu = DSU(nax);
    int ptr = 0;
    FOR(sz(tree)) {
        S t = tree[i];
        while(ptr < sz(ppl) && ppl[ptr].r < t.r) {
            FOR(k, 6) {
                if(dsu.same(C1[k], C2[k])) {
                    ans[ppl[ptr].x] &= mask(MS[k], ppl[ptr].y);
                }
            }
            ptr++;
        }
        dsu.merge(t.x, t.y);
    }

    FOR(i, 1, m + 1) {
        FOR(k, 4) {
            if(ans[i] >> k & 1) pt(k + 1);
        }
        nl;
    }
    return 0;
}

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