Submission #1288600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288600		behesht	Park (BOI16_park)	C++20	100 / 100	276 ms	59616 KiB

park

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e9 + (35 / 10); // 35 ---> 36
const int MAXN = 2e5 + (35 / 10); // 35 ---> 36

vector <arr(2)> c[5][5];
vector <arr(3)> Q, e;
arr(3) a[MAXN];
arr(2) cc[5];
int p[MAXN];
string ans[MAXN];

int dis(arr(3) x, arr(3) y){

    auto [x1, y1, r1] = x;
    auto [x2, y2, r2] = y;

    int res = abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2);
    int eli = sqrtl(res);

    // if(eli * eli != res)
    //  eli++;

    res = eli;
    res -= r1 + r2;

    return res;
}

int get(int x){
    
    if(p[x] == x)
        return x;
    
    return p[x] = get(p[x]);
}

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

    cc[1] = {1, 2};
    cc[2] = {1, 3};
    cc[3] = {0, 3};
    cc[4] = {0, 2};

    // 1 2
    c[1][2].pb({1, 0});

    // 1 3
    c[1][3].pb({2, 3});
    c[1][3].pb({0, 1});

    // 1 4
    c[1][4].pb({2, 3});

    // 2 3
    c[2][3].pb({2, 3});

    // 2 4
    c[2][4].pb({0, 1});
    c[2][4].pb({2, 3});

    // 3 4
    c[3][4].pb({0, 1});

    for(int i = 1; i <= 4; i++){
        for(int j = 1; j < i; j++){
            c[j][i].pb(cc[i]);
            c[j][i].pb(cc[j]);
            c[i][j] = c[j][i];
        }
    }

    // for(int i = 1; i <= 4; i++){
    //  d2(i, 1);

    //  for(auto [x, y] : c[i][1])
    //      d2(x, y);
    //  cout << endl;

    //  for(auto [x, y] : c[1][i])
    //      d2(x, y);
    //  cout << endl;
    // }

    int n, q;
    cin >> n >> q;

    int X, Y;
    cin >> X >> Y;

    n += 4;

    for(int i = 4; i < n; i++){

        for(int j = 0; j < 3; j++)
            cin >> a[i][j];

        auto [x, y, r] = a[i];

        for(int j = 4; j < i; j++)
            e.pb({dis(a[i], a[j]), i, j});
        
        e.pb({Y - y - r, i, 0});
        e.pb({y - r, i, 1});
        e.pb({x - r, i, 2});
        e.pb({X - x - r, i, 3});;
    }

    for(int i = 0; i < q; i++){
        int x, r;
        cin >> r >> x;

        Q.pb({r * 2, x, i});
    }

    sort(e.begin(), e.end(), greater<arr(3)>());
    sort(Q.begin(), Q.end());

    // for(auto [w, u, v] : e)
    //  d3(w, u, v);

    for(int i = 0; i < n; i++)
        p[i] = i;
    
    for(auto [r, x, ind] : Q){

        // d3(r, x, ind);

        while(!e.empty()){

            auto [w, u, v] = e.back();
            // d3(w, u, v);

            if(w >= r)
                break;
            
            e.pop_back();

            if(get(u) != get(v))
                p[get(u)] = get(v);
        }
        // cout << endl;
        
        for(int i = 1; i <= 4; i++){
            bool f = 1;

            for(auto [x, y] : c[x][i])
                f &= (get(x) != get(y));
            
            if(f)
                ans[ind] += '0' + i;
        }
    }

    for(int i = 0; i < q; i++)
        cout << ans[i] << endl;
}

// Ey To Bahane! :_)))

// -------------<3------------- //
/*
Magasan dor shirini: 

1. MAXN
2. Input style
3. index or value? Masale In Ast!   
4. MOD 

*/

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