제출 #940010

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940010		Darren0724	Park (BOI16_park)	C++17	100 / 100	518 ms	62224 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
#define int long long 
const int N=2005;
const int INF=1e18;
int n,q,h,w;
vector<int> x(N),y(N),r(N),pa(N);
vector ans(100005,vector<int>(4));
int Find(int k){
    return pa[k]==k?k:pa[k]=Find(pa[k]);
}
void onion(int a,int b){
    a=Find(a),b=Find(b);
    if(a==b)return;
    pa[a]=b;
}
int connect(int a,int b){
    return Find(a)==Find(b);
}
/*
n   -> bottom
n+1 -> right
n+2 -> top
n+3 -> left
*/
int cal(int t1,int t2,int k){
    if(t1>t2)swap(t1,t2);
    if(t2>=n){
        if(t1>=n){
            return 0;
        }
        else{
            if(t2==n)  return y[t1]-r[t1]-k*2<0;
            if(t2==n+1)return x[t1]+r[t1]+k*2>h;
            if(t2==n+2)return y[t1]+r[t1]+k*2>w;
            if(t2==n+3)return x[t1]-r[t1]-k*2<0;
        }
    }
    else{
        int dis=(x[t1]-x[t2])*(x[t1]-x[t2])+(y[t1]-y[t2])*(y[t1]-y[t2]);
        int r1=r[t1]+r[t2]+k*2;
        return r1*r1>dis;
    }
    assert(false);
}
int32_t main() {
    LCBorz;
    iota(all(pa),0);
    cin>>n>>q;
    cin>>h>>w;
    for(int i=0;i<n;i++){
        cin>>x[i]>>y[i]>>r[i];
    }
    vector<pair<int,pair<int,int>>> ask(q);
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        ask[i]={a,{i,b-1}};
    }
    sort(all(ask));
    vector<pair<int,pair<int,int>>> dis;
    for(int i=0;i<=n+3;i++){
        for(int j=i+1;j<=n+3;j++){
            int l=0,r=max(h,w);
            while(r-l>1){
                int m=(l+r)>>1;
                (cal(i,j,m)?r:l)=m;
            }
            dis.push_back({l,{i,j}});
        }
    }
    sort(all(dis));
    for(auto [a,b1]:dis){
        auto [b,c]=b1;
    }
    int ptr=0;
    for(int i=0;i<q;i++){
        auto [r,b1]=ask[i];
        auto [id,t1]=b1;
        while(ptr<dis.size()&&dis[ptr].first<r){
            auto [a,b]=dis[ptr].second;
            onion(a,b);
            ptr++;
        }
        auto f=[t1](int p1,int p2)->int {
            return !connect(n+(t1+p1)%4,n+(t1+p2)%4); 
        };
        ans[id][t1]=1;
        if(f(0,1)&&f(0,2)&&f(0,3))ans[id][(t1+1)%4]=1;
        if(f(0,2)&&f(0,3)&&f(1,2)&&f(1,3))ans[id][(t1+2)%4]=1;
        if(f(0,3)&&f(1,3)&&f(2,3))ans[id][(t1+3)%4]=1;
    }
    for(int i=0;i<q;i++){
        for(int j=1;j<=4;j++){
            if(ans[i][j-1])cout<<j;
        }
        cout<<endl;
    }
    
    return 0;
}

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

park.cpp: In function 'int32_t main()':
park.cpp:76:14: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   76 |         auto [b,c]=b1;
      |              ^~~~~
park.cpp:82:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         while(ptr<dis.size()&&dis[ptr].first<r){
      |               ~~~^~~~~~~~~~~

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