Submission #385781

#	Time	Username	Problem	Language	Result	Execution time	Memory
385781		erfanmir	Park (BOI16_park)	C++11	27 / 100	525 ms	70908 KiB

park

// In the name of god

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair
ll poww(ll a, ll b, ll md) {
    ll ans = 1;
    for(; b; b >>= 1, a = a * a % md){
        if(b & 1){
            ans = ans * a % md;
        }
    }
    return ans % md;
}

const int MAXN = 3e3 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
const ld ep = 1e-12;
int n, m, w, h;
int par[MAXN], sz[MAXN];
ll x[MAXN], y[MAXN], r[MAXN];
int ans[4][4];
vector<int> res[200010];
vector<pair<ld, pii> > edge;
vector<pair<pair<ld, ll>, int> > q;

int getroot(int v){
    if(par[v] == v){
        return v;
    }
    return par[v] = getroot(par[v]);
}

void merg(int v, int u){
    v = getroot(v);
    u = getroot(u);
    if(v == u){
        return;
    }
    if(sz[v] < sz[u]){
        swap(v, u);
    }
    par[u] = v;
    sz[v] += sz[u];
}

void preprocess(){
    int st[4];
    for(int i = 0; i < 4; i++){
        st[i] = getroot(n + i);
    }
    ans[0][1] = (st[0] != st[1]) && (st[1] != st[2]) && (st[1] != st[3]);
    ans[1][2] = (st[1] != st[2]) && (st[2] != st[3]) && (st[2] != st[0]);
    ans[2][3] = (st[2] != st[3]) && (st[3] != st[0]) && (st[3] != st[1]);
    ans[0][2] = (st[0] != st[1]) && (st[2] != st[3]) && (st[0] != st[2]) && (st[1] != st[3]);
    ans[1][3] = (st[0] != st[3]) && (st[2] != st[1]) && (st[0] != st[2]) && (st[1] != st[3]);
    ans[0][3] = (st[3] != st[0]) && (st[0] != st[1]) && (st[0] != st[2]);
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(i == j){
                ans[i][j] = 1;
            }
            if(i > j){
                ans[i][j] = ans[j][i];
            }
        }
    }
}

int main()
{
    scanf("%d %d %d %d", &n, &m, &w, &h);
    for(int i = 0; i < n; i++){
        scanf("%lld %lld %lld\n", x + i, y + i, r + i);
        ld tmp = x[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n)));
        tmp = w - x[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n + 2)));
        tmp = y[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n + 1)));
        tmp = h - y[i] - r[i];
        edge.push_back(mp(tmp, mp(i, n + 3)));
        for(int j = 0; j < i; j++){
            tmp = sqrt((ld)abs(x[i] - x[j]) * abs(x[i] - x[j]) + (ld)abs(y[i] - y[j]) * abs(y[i] - y[j])) - (ld)r[i] - (ld)r[j];
            edge.push_back(mp(tmp, mp(j, i)));
        }
    }
    for(int i = 0; i < m; i++){
        ll a, b;
        scanf("%lld %lld", &a, &b);
        a *= 2;
        b--;
        q.push_back(mp(mp((ld)a, b), i));
    }
    sort(all(edge));
    sort(all(q));
    for(int i = 0; i < n + 4; i++){
        par[i] = i;
        sz[i] = 1;
    }
    int cnt = 0;
    for(int i = 0; i < m; i++){
        while(cnt < (int)edge.size() && ep < q[i].F.F - edge[cnt].F){
            merg(edge[cnt].S.F, edge[cnt].S.S);
            preprocess();
            cnt++;
        }
        for(int j = 0; j < 4; j++){
            if(ans[q[i].F.S][j]){
                res[q[i].S].push_back(j + 1);
            }
        }
    }
    for(int i = 0; i < m; i++){
        for(auto u : res[i]){
            printf("%d", u);
        }
        printf("\n");
    }
}

Compilation message (stderr)

park.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
park.cpp: In function 'int main()':
park.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d %d %d %d", &n, &m, &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |         scanf("%lld %lld %lld\n", x + i, y + i, r + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |         scanf("%lld %lld", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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