Submission #989998

#	Time	Username	Problem	Language	Result	Execution time	Memory
989998		AlperenT_	Park (BOI16_park)	C++17	100 / 100	376 ms	63380 KiB

park

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn =2e5+10  ,  N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e18  , maxk = 2022  , mod =998244353;
int par[maxn] , dis[maxn] ,x[maxn] ,y[maxn] ,n , m , h ,w , r[maxn] ;
vector <pii>G[maxn] ;
int find(int v){
    if(par[v] == -1)return v;
    return par[v] = find(par[v]) ;
}

void dfs(int v, int p =-1){
    for(auto [u,w]: G[v]){
        if(u == p)continue ;
        dis[u]= max(w , dis[v]) ;
        dfs(u , v);
    }
}

int cal(int v ,int u){
    rep(i , 0 ,n+4){
        dis[i] = -inf ;
    }
    dis[v] = 0;
    dfs(v);
    return dis[u] ;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> w >> h;
    rep(i ,0 ,n-1){
        cin >> x[i] >> y[i] >> r[i] ;
    }
    rep(i , 0 , n+3){
        par[i] = -1 ;
    }
    vector<pair<int,pii> > vec;
    rep(i ,0 ,n-1){
        rep(j , i+1 , n-1){
            int f = abs(x[i]-x[j])*abs(x[i]-x[j]) +abs(y[i]-y[j])*abs(y[i]-y[j])  ;
            int L = 0 ,R = 2e9 ;
            while(R-L>1){
                int mid = (L+R)/2 ;
                if(mid*mid <= f){
                    L = mid ;
                }else{
                    R = mid ;
                }
            } 
            vec.pb({L-r[i]-r[j] , {i,j}}) ;
        }
    }
    rep(i ,0, n-1){
        vec.pb({x[i]-r[i] , {i , n+3}});
        vec.pb({w-x[i]-r[i] , {i , n+1}});
        vec.pb({y[i]-r[i] , {i , n}});
        vec.pb({h-y[i]-r[i], {i , n+2}});
    }
    sort(all(vec));
    rep(i , 0 ,sz(vec)-1){
        int w= vec[i].F, v = vec[i].S.F,  u = vec[i].S.S ;
        if(find(v) == find(u))continue ;
        G[v].pb({u,w});
        G[u].pb({v,w});
        par[find(v)] = find(u) ;
    }
    int d[4][4];
    rep(i , 0 , 3){
        rep(j , 0 , 3){
            if(i == j)continue ;
            d[i][j] = cal(n+i , n+j) ;
        }
    }
    while(m--){
        int r , t ;
        cin >> r >> t ;t--;
        string ans ;
        rep(i , 0 , 3){
            if(i == t){
                ans += (char)((i+1)+'0');
                continue ;
            }
            vector <int> a, b ;
            int x = t , y = i ;
            while(x != y){
                a.pb(x);
                x = (x+1)%4;
            }
            x = i ,y = t ;
            while(x!=y){
                b.pb(x);
                x = (x+1)%4 ;
            }
            bool ok =0 ;
            rep(j , 0, sz(a)-1){
                rep(k , 0 ,sz(b)-1){
                    if(d[a[j]][b[k]] < 2*r){
                        ok =1 ;
                    }
                }
            }
            if(ok == 0){
                ans += (char)((i+1)+'0') ;
            }
        }
        cout << ans << "\n"; 
    }
}

/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/

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