oj.uz

Submission #373087

# Submission time Handle Problem Language Result Execution time Memory
373087 2021-03-03T09:22:43 Z alirezasamimi100 Park (BOI16_park) C++17
100 / 100
 443 ms 57964 KB 
#include <bits/stdc++.h>
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
using namespace std;
using ll = long long int;
#define F first
#define S second
#define pb push_back
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=2e3+10,LN=20,M=1e5+10,SQ=350,inf=1e9;
const ll INF=1e18;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
ll n,q,w,h,X[N],Y[N],R[N],P[N];
vector<pair<double,pll>> ed;
vector<pair<pair<double,ll>,ll>> qu;
vector<ll> ans[M];
ll gp(ll x){
    return P[x]?P[x]=gp(P[x]):x;
}
void uni(ll v, ll u){
    v=gp(v),u=gp(u);
    if(v!=u) P[u]=v;
}
int main(){
    fast_io;
    cin >> n >> q >> w >> h;
    for(ll i=1; i<=n; i++){
        cin >> X[i] >> Y[i] >> R[i];
        ed.pb({X[i]-R[i],{i,n+1}});
        ed.pb({Y[i]-R[i],{i,n+2}});
        ed.pb({w-X[i]-R[i],{i,n+3}});
        ed.pb({h-Y[i]-R[i],{i,n+4}});
    }
    for(ll i=1; i<=n; i++){
        for(ll j=i+1; j<=n; j++){
            ll x=X[i]-X[j],y=Y[i]-Y[j],r=R[i]+R[j];
            double t=sqrt(x*x+y*y)-r;
            ed.pb({t,{i,j}});
        }
    }
    sort(ed.begin(),ed.end());
    ll j=0;
    for(ll i=1; i<=q; i++){
        ll r,e;
        cin >> r >> e;
        qu.pb({{2*r,e},i});
    }
    sort(qu.begin(),qu.end());
    for(ll i=0; i<q; i++){
        ll e=qu[i].F.S,k=qu[i].S;
        while(j<ed.size() && ed[j].F<qu[i].F.F){
            uni(ed[j].S.F,ed[j].S.S);
            j++;
        }
        if(e==1){
            ans[k].pb(1);
            ll p[5];
            for(ll x=1; x<5; x++) p[x]=gp(n+x);
            if(p[2]!=p[1] && p[2]!=p[3] && p[2]!=p[4]) ans[k].pb(2);
            if(p[1]!=p[2] && p[1]!=p[3] && p[1]!=p[4]) ans[k].pb(4);
            if(p[1]!=p[2] && p[1]!=p[3] && p[4]!=p[3] && p[4]!=p[2]) ans[k].pb(3);
        }
        if(e==2){
            ans[k].pb(2);
            ll p[5];
            for(ll x=1; x<5; x++) p[x]=gp(n+x);
            if(p[3]!=p[1] && p[3]!=p[4] && p[3]!=p[2]) ans[k].pb(3);
            if(p[2]!=p[1] && p[2]!=p[3] && p[2]!=p[4]) ans[k].pb(1);
            if(p[3]!=p[2] && p[3]!=p[1] && p[4]!=p[2] && p[4]!=p[1]) ans[k].pb(4);
        }
        if(e==3){
            ans[k].pb(3);
            ll p[5];
            for(ll x=1; x<5; x++) p[x]=gp(n+x);
            if(p[4]!=p[1] && p[4]!=p[2] && p[4]!=p[3]) ans[k].pb(4);
            if(p[3]!=p[2] && p[3]!=p[4] && p[3]!=p[1]) ans[k].pb(2);
            if(p[2]!=p[1] && p[2]!=p[4] && p[3]!=p[1] && p[3]!=p[4]) ans[k].pb(1);
        }
        if(e==4){
            ans[k].pb(4);
            ll p[5];
            for(ll x=1; x<5; x++) p[x]=gp(n+x);
            if(p[1]!=p[2] && p[1]!=p[3] && p[1]!=p[4]) ans[k].pb(1);
            if(p[4]!=p[2] && p[4]!=p[1] && p[4]!=p[3]) ans[k].pb(3);
            if(p[1]!=p[4] && p[1]!=p[3] && p[2]!=p[3] && p[2]!=p[4]) ans[k].pb(2);
        }
        sort(ans[k].begin(),ans[k].end());
    }
    for(ll i=1; i<=q; i++){
        for(ll j : ans[i]) cout << j;
        cout << '\n';
    }
    return 0;
}

Compilation message

park.cpp: In function 'int main()':
park.cpp:72:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while(j<ed.size() && ed[j].F<qu[i].F.F){
      |               ~^~~~~~~~~~

Subtask #1
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 52132 KB Output is correct
2 Correct 344 ms 52156 KB Output is correct
3 Correct 357 ms 52132 KB Output is correct
4 Correct 344 ms 52284 KB Output is correct
5 Correct 341 ms 52260 KB Output is correct
6 Correct 342 ms 52132 KB Output is correct
7 Correct 330 ms 52260 KB Output is correct
8 Correct 318 ms 52332 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10204 KB Output is correct
2 Correct 83 ms 10076 KB Output is correct
3 Correct 82 ms 9820 KB Output is correct
4 Correct 81 ms 10076 KB Output is correct
5 Correct 78 ms 10204 KB Output is correct
6 Correct 84 ms 10972 KB Output is correct
7 Correct 79 ms 10080 KB Output is correct
8 Correct 80 ms 10080 KB Output is correct

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 52132 KB Output is correct
2 Correct 344 ms 52156 KB Output is correct
3 Correct 357 ms 52132 KB Output is correct
4 Correct 344 ms 52284 KB Output is correct
5 Correct 341 ms 52260 KB Output is correct
6 Correct 342 ms 52132 KB Output is correct
7 Correct 330 ms 52260 KB Output is correct
8 Correct 318 ms 52332 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 82 ms 10204 KB Output is correct
12 Correct 83 ms 10076 KB Output is correct
13 Correct 82 ms 9820 KB Output is correct
14 Correct 81 ms 10076 KB Output is correct
15 Correct 78 ms 10204 KB Output is correct
16 Correct 84 ms 10972 KB Output is correct
17 Correct 79 ms 10080 KB Output is correct
18 Correct 80 ms 10080 KB Output is correct
19 Correct 424 ms 57496 KB Output is correct
20 Correct 427 ms 57584 KB Output is correct
21 Correct 431 ms 57964 KB Output is correct
22 Correct 415 ms 57200 KB Output is correct
23 Correct 443 ms 57612 KB Output is correct
24 Correct 410 ms 57600 KB Output is correct