제출 #385767

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385767		erfanmir	Park (BOI16_park)	C++17	27 / 100	525 ms	66244 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 = 2e3 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
int n, m, w, h;
int par[MAXN], sz[MAXN];
ll x[MAXN], y[MAXN], r[MAXN];
int ans[4][4];
int res[100010];
vector<pair<ld, pii> > edge;
vector<pair<pll, int> > q;

int getroot(int v){
    return par[v] == v ? v : 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);
    }
    for(int i = 0; i < 3; i++){
        ans[i][i + 1] = (st[i] != st[(i + 1) % 4]) && (st[(i + 1) % 4] != st[(i + 2) % 4]) && (st[(i + 1) % 4] != st[(i + 3) % 4]);
    }
    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];
        tmp = max(tmp, (ld)0);
        edge.push_back(mp(tmp, mp(i, n)));
        tmp = w - x[i] - r[i];
        tmp = max(tmp, (ld)0);
        edge.push_back(mp(tmp, mp(i, n + 2)));
        tmp = y[i] - r[i];
        tmp = max(tmp, (ld)0);
        edge.push_back(mp(tmp, mp(i, n + 1)));
        tmp = h - y[i] - r[i];
        tmp = max(tmp, (ld)0);
        edge.push_back(mp(tmp, mp(i, n + 3)));
        for(int j = 0; j < i; j++){
            tmp = sqrt((ld)(x[i] - x[j]) * (x[i] - x[j]) + (ld)(y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j];
            tmp = max(tmp, (ld)0);
            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(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() && edge[cnt].F < (ld)q[i].F.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] *= 10;
                res[q[i].S] += j + 1;
            }
        }
    }
    for(int i = 0; i < m; i++){
        printf("%d\n", res[i]);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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