oj.uz

Submission #940010

# Submission time Handle Problem Language Result Execution time Memory
940010 2024-03-07T03:45:08 Z Darren0724 Park (BOI16_park) C++17
100 / 100
 518 ms 62224 KB 
#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;
}

Compilation message

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.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 57884 KB Output is correct
2 Correct 456 ms 57304 KB Output is correct
3 Correct 453 ms 57508 KB Output is correct
4 Correct 458 ms 58768 KB Output is correct
5 Correct 455 ms 56936 KB Output is correct
6 Correct 461 ms 58276 KB Output is correct
7 Correct 460 ms 59144 KB Output is correct
8 Correct 442 ms 58276 KB Output is correct
9 Correct 5 ms 7512 KB Output is correct
10 Correct 6 ms 7328 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 10876 KB Output is correct
2 Correct 46 ms 11852 KB Output is correct
3 Correct 48 ms 11796 KB Output is correct
4 Correct 46 ms 11860 KB Output is correct
5 Correct 52 ms 11852 KB Output is correct
6 Correct 51 ms 11856 KB Output is correct
7 Correct 42 ms 11300 KB Output is correct
8 Correct 40 ms 11360 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 460 ms 57884 KB Output is correct
2 Correct 456 ms 57304 KB Output is correct
3 Correct 453 ms 57508 KB Output is correct
4 Correct 458 ms 58768 KB Output is correct
5 Correct 455 ms 56936 KB Output is correct
6 Correct 461 ms 58276 KB Output is correct
7 Correct 460 ms 59144 KB Output is correct
8 Correct 442 ms 58276 KB Output is correct
9 Correct 5 ms 7512 KB Output is correct
10 Correct 6 ms 7328 KB Output is correct
11 Correct 51 ms 10876 KB Output is correct
12 Correct 46 ms 11852 KB Output is correct
13 Correct 48 ms 11796 KB Output is correct
14 Correct 46 ms 11860 KB Output is correct
15 Correct 52 ms 11852 KB Output is correct
16 Correct 51 ms 11856 KB Output is correct
17 Correct 42 ms 11300 KB Output is correct
18 Correct 40 ms 11360 KB Output is correct
19 Correct 511 ms 61204 KB Output is correct
20 Correct 499 ms 62212 KB Output is correct
21 Correct 493 ms 62124 KB Output is correct
22 Correct 496 ms 61108 KB Output is correct
23 Correct 518 ms 61608 KB Output is correct
24 Correct 491 ms 62224 KB Output is correct