제출 #1135596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1135596		vasyamer	Park (BOI16_park)	C++20	0 / 100	436 ms	49912 KiB

park

// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
 
// #define _GLIBCXX_DEBUG
// #define _GLIBCXX_DEBUG_PEDANTIC
 
#include <iomanip>
#include <cassert>
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <array>
#include <numeric>
#include <queue>
#include <deque>
#include <bitset>
#include <cmath>
#include <climits>
#include <cstdint>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>
 
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;

 
const int MOD = 998244353;
const long double PI = 3.141592653589793;
using ll = long long;
const ll INF = 1e18;
 
#define int ll

// --------> sashko123`s defines:

#define itn int     //Vasya sorry :(
#define p_b push_back
#define fi first
#define se second
#define pii std::pair<int, int>
#define oo LLONG_MAX
#define big INT_MAX
#define elif else if

int input()
{
    int x;
    cin >> x;
    return x;
}

// ----------> end of sashko123`s defines (thank you Vasya <3)

// template<typename K, typename V>
// using hash_table = cc_hash_table<K, V, hash<K>>;

// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;


struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(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;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

int my_sqrt(int x) {
    if (x <= 0)
        return 0;
    int l = 0, r = sqrt(x) + 10;
    while (r - l > 1) {
        int m = (r + l) / 2;
        if (m * m >= x)
            r = m;
        else
            l = m;
    }
    return r;
}

void solve() {
    int n, m;
    cin >> n >> m;
    int w, h;
    cin >> w >> h;
    vector<tuple<int, int, int>> tree;
    for (int i = 0; i < n; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        tree.push_back({x, y, r});
    }
    vector<pair<int, pii>> all;
    for (int i = 0; i < n; i++) {
        auto [x1, y1, r1] = tree[i];
        for (int j = i + 1; j < n; j++) { 
            auto [x2, y2, r2] = tree[j];
            int len = my_sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) - r1 - r2;
            all.push_back({len, {i, j}});
        }
    }
    for (int i = 0; i < n; i++) {
        auto [x, y, r] = tree[i];

        int left = (x - r);
        all.push_back({left, {i, n}});

        int up = h - (y + r);
        all.push_back({up, {i, n + 1}});

        int right = w - (x + r);
        all.push_back({right, {i, n + 2}});

        int down = (y - r);
        all.push_back({down, {i, n + 3}});
    }

    sort(all.begin(), all.end());

    vector<tuple<int, int, int>> qq;
    for (int i = 0; i < m; i++) {
        int r, e;
        cin >> r >> e;
        qq.push_back({r * 2, e, i});
    }
    sort(qq.begin(), qq.end());

    dsu dd(n + 4);

    vector<vector<int>> ANS(m);

    int T = 0;
    for (auto [r, e, id]: qq) {
        // cerr << "CUR " << r << " " << id << endl;
        while (T < all.size() && all[T].first <= r) {
            auto [i, j] = all[T].second;
            // cerr << "ADD " << i << " " << j << " -> " << all[T].first << endl;
            dd.merge(i, j);
            T++;
        }
        vector<int> ans;
        if (e == 1) {
            ans = {1};

            if (!dd.same(n, n + 3) && !dd.same(n + 1, n + 3) && !dd.same(n + 3, n + 2)) {
                ans.push_back(2);
            }
            if (!dd.same(n, n + 3) && !dd.same(n + 1, n + 3) && !dd.same(n + 0, n + 2) && !dd.same(n + 1, n + 2)) {
                ans.push_back(3);
            }
            if (!dd.same(n, n + 1) && !dd.same(n, n + 3) && !dd.same(n, n + 2)) {
                ans.push_back(4);
            }
        } else if (e == 2) {
            if (!dd.same(n + 2, n + 3) && !dd.same(n + 1, n + 3) && !dd.same(n + 0, n + 3)) {
                ans.push_back(1);
            }
            ans.push_back(2);
            if (!dd.same(n + 2, n + 3) && !dd.same(n + 0, n + 2) && !dd.same(n + 1, n + 2)) {
                ans.push_back(3);
            }
            if (!dd.same(n + 0, n + 1) && !dd.same(n + 0, n + 2) && !dd.same(n + 1, n + 3) && !dd.same(n + 2, n + 3)) {
                ans.push_back(4);
            }
        } else if (e == 3) {
            if (!dd.same(n + 1, n + 2) && !dd.same(n + 0, n + 3) && !dd.same(n + 1, n + 3) && !dd.same(n + 0, n + 2)) {
                ans.push_back(1);
            }
            if (!dd.same(n + 1, n + 2) && !dd.same(n + 2, n + 3) && !dd.same(n + 0, n + 2)) {
                ans.push_back(2);
            }
            ans.push_back(3);
            if (!dd.same(n + 0, n + 1) && !dd.same(n + 1, n + 3) && !dd.same(n + 1, n + 2)) {
                ans.push_back(4);
            }
        } else {
            if (!dd.same(n + 0, n + 1) && !dd.same(n + 0, n + 3) && !dd.same(n + 0, n + 2)) {
                ans.push_back(1);
            }
            if (!dd.same(n + 0, n + 1) && !dd.same(n + 2, n + 3) && !dd.same(n + 0, n + 2) && !dd.same(n + 1, n + 3)) {
                ans.push_back(2);
            }
            if (!dd.same(n + 0, n + 1) && !dd.same(n + 1, n + 3) && !dd.same(n + 1, n + 2)) {
                ans.push_back(3);
            }
            ans.push_back(4);
        }   

        ANS[id] = ans;
    }

    for (int i = 0; i < m; i++) {
        for (auto j : ANS[i])
            cout << j;
        cout << endl;
    }

}	
 
int32_t main(int32_t argc, const char * argv[]) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    // insert code here...

    int tt= 1;
    // std::cin >> tt;
	for (int t = 1; t <= tt; t++) {
		// cout << "Case #" << t << ": ";
        solve();
    }
    return 0;
}

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