Submission #1279965

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279965		longdeptrai	Park (BOI16_park)	C++20	0 / 100	535 ms	85680 KiB

park

#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;
#define LongDepTrai "park"
#define ll long long
#define int long long
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) int((x).size())
#define order_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>

inline ll add(ll a, ll b, ll mod){ a += b; if(a >= mod) a -= mod; return a; }
inline ll sub(ll a, ll b, ll mod){ a -= b; if(a < 0) a += mod; return a; }
inline ll mul(ll a, ll b, ll mod){ return ( (ll)a * b ) % mod; }

static mt19937_64 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
const int N=2e3+9;
int n,m,par[N],w,h,l[5][5];
int acs(int u){
    if(par[u]==u) return u;
    return (par[u]=acs(par[u]));
}
void join(int u,int v){
     u=acs(u);
     v=acs(v);
    if(u!=v){
        par[u]=v;
    }
}
bool same(int i,int j){
    return(acs(i)==acs(j));
}
struct circle{
    int x,y,r;
} a[N];
int dist(int i,int j){
    return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y))-a[i].r-a[j].r;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    if(fopen(LongDepTrai".inp","r")){
        freopen(LongDepTrai".inp","r",stdin);
        freopen(LongDepTrai".out","w",stdout);
    }
    cin>>n>>m>>w>>h;
    vector<iii> ed;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].r;
        ed.pb({a[i].y-a[i].r,{i,n+1}});
        ed.pb({a[i].x-a[i].r,{i,n+3}});
        ed.pb({h-a[i].y-a[i].r,{i,n+2}});
        ed.pb({w-a[i].x-a[i].r,{i,n+4}});
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ed.pb({dist(i,j),{i,j}});
        }
    }
    sort(ed.begin(),ed.end());
    for(iii x:ed){
        cout<<x.fi<<" "<<x.se.fi<<" "<<x.se.se<<"\n";
    }
    for(int i=1;i<=n+4;i++) par[i]=i;
    for(int i=1;i<4;i++){
        for(int j=i+1;j<=4;j++){
            l[i][j]=-1;
        }
    }

    for(iii x:ed){
        join(x.se.fi,x.se.se);
        for(int i=1;i<=3;i++){
            for(int j=i+1;j<=4;j++){
                if(same(n+i,n+j) && l[i][j]==-1){
                    l[i][j]=x.fi;
                }
            }
        }
    }
    for(int i=1;i<4;i++){
        for(int j=i+1;j<=4;j++){
            cout<<i<<" "<<j<<" "<<l[i][j]<<"\n";
        }
    }

    for(int i=1;i<=m;i++){
        int r,e;
        cin>>r>>e;
        int ans[5];
        r+=r;
        memset(ans,0,sizeof(ans));
        if(e==1){
            ans[1]=1;
            if(r<=l[3][4] && r<=l[1][3] && r<=l[1][2] && r<=l[2][4]) ans[3]=1;
            if(r<=l[1][2] && r<=l[1][3] && r<=l[1][4]) ans[2]=1;
            if(r<=l[1][3] && r<=l[3][4] && r<=l[2][3]) ans[4]=1;
        }
        if(e==2){
            ans[2]=1;
            if(r<=l[2][3] && r<=l[1][4] && r<=l[3][4] && r<=l[1][2]) ans[4]=1;
            if(r<=l[2][4] && r<=l[3][4] && r<=l[1][4]) ans[3]=1;
            if(r<=l[1][3] && r<=l[1][2] && r<=l[1][4]) ans[1]=1;
        }
        if(e==3){
            ans[3]=1;
            if(r<=l[2][4] && r<=l[3][4] && r<=l[1][2] && r<=l[1][3]) ans[1]=1;
            if(r<=l[2][4] && r<=l[1][2] && r<=l[2][3]) ans[4]=1;
            if(r<=l[2][4] && r<=l[3][4] && r<=l[1][4]) ans[2]=1;
        }
        if(e==4){
            ans[4]=1;
            if(r<=l[2][3] && r<=l[3][4] && r<=l[1][2] && r<=l[1][4]) ans[2]=1;
            if(r<=l[2][3] && r<=l[3][4] && r<=l[1][3]) ans[1]=1;
            if(r<=l[2][3] && r<=l[1][2] && r<=l[2][4]) ans[3]=1;
        }
        for(int j=1;j<=4;j++){
            if(ans[j]) cout<<j;
        }
        cout<<"\n";
    }



    return 0;
}

Compilation message (stderr)

park.cpp: In function 'int main()':
park.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(LongDepTrai".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(LongDepTrai".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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