Submission #237572

#	Time	Username	Problem	Language	Result	Execution time	Memory
237572		Goolakh	Park (BOI16_park)	C++17	100 / 100	1629 ms	25524 KiB

park

/// RESTRICTED AREA
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Os")

/*				Who knew evil girls had the prettiest face					*/

/*				I'm not god, baby / I don't forgive, baby					*/

/*				I'm like "Hey, what's up? Hello"
				Seen yo pretty ass soon as you came in the door
				I just wanna chill, got a sack for us to roll
				Married to the money, introduced her to my stove
				Showed her how to whip it, now she remixin' for low
				She my trap queen, let her hit the bando
				We be countin' up, watch how far them bands go
				We just set a goal, talkin' matchin' Lambos
				At fifity six a gram, five a hundred grams though
				Man, I swear I love her, how she work the damn pole
				Hit the strip club, we be lettin' bands go
				Everybody hatin', we just call them fans, though
				In love with the money, I ain't never lettin' go			*/

/*				We pop out at your party, I'm with the gang
				And it's gon' be a robbery, so tuck ya chain
				I'm a killer girl, I'm sorry, but I cannot change
				We ain't aiming for your body, shots hit you brain
				We come from poverty, man, we ain't have a thing
				It's a lot of animosity, but they won't say my name
				Them killers rock with me, lil' nigga, don't get banged
				'Cause they'll do that job for me while I hop on a plane	*/

/*				I take you to the candy shop								*/

/*				Baby, let me put your panties to the side
				I'ma make you feel alright
				'Cause I'ma give you what you need, yeah					*/

/*				Ooooh ooh, it's me, myself and I
				Solo ride until I die, 'cause I got me for life				*/

/*				So I ball So hard, muh'fuckas wanna find me					*/

/*				Bitch, where you when I was walkin'?
				Now I run the game, got the whole world talkin'				*/
 
/*				Niggas been counting me out
				I'm counting my bullets, I'm loading my clips
				I'm writing down names, I'm making a list					*/

/*				Fuck your friendship, I meant it							*/

/*				The Chanel or Balenciaga, Louis and Vuitton
				She know I got Fendi, Prada when I hit Milan				*/

/*				I ran away, I don't think I'm coming back home				*/
 
#define F first
#define S second
#define pb emplace_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define mp make_pair
 
typedef int ll;
typedef long double ld;
typedef pair<ll,ll> pll;
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e3+10, maxm=1e3+10, lg=20, mod=1e9+7, inf=1e18;

#define tapal tuple<int,int,int>

//typedef tuple<ll,ll,ll> tapal;

ll n,m,w,h,par[maxn];
ll x[maxn],y[maxn],r[maxn];
ll d[4][4];
vector<pll> g[4];

ll gpar(ll u){ return par[u]= par[u]==u ? u:gpar(par[u]); }
void mrg(ll v,ll u){ par[gpar(v)]=gpar(u); }
bool cmp(tapal a,tapal b){ return get<2>(a) < get<2>(b) ; }

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
    g[1]={{2, 3}, {0, 2}, {2, 1}};
    g[2]={{1, 2}, {1, 3}, {0, 2}, {0, 3}};
    g[3]={{1, 3}, {0, 1}, {1, 2}};

 	iota(par,par+maxn,0);
    cin>>n>>m>>w>>h;
	vector<tapal> E;
  	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i]>>r[i];
		E.pb(i,n  ,h-y[i]-r[i]);
	    E.pb(i,n+1,x[i]-r[i]);
	    E.pb(i,n+2,y[i]-r[i]);
	    E.pb(i,n+3,w-x[i]-r[i]);
    }
 	for(int i=0;i<n;i++)for(int j=i+1;j<n;j++) E.pb(i,j,(ll)(hypot(x[i]-x[j],y[i]-y[j]))-r[i]-r[j]);
    sort(all(E),cmp);
	for(int i=0;i<4;i++)for(int j=0;j<4;j++) d[i][j]=(i==j ? mod:-1);
    for(auto x:E){
        ll u,v,w; tie(u,v,w)=x;
		mrg(u,v);
        for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(i!=j)for(auto z:g[(j-i+4)%4]){
        	ll a,b; tie(a, b)=z;
            a=n+((a+i)%4), b=n+((b+i)%4);
            if(gpar(a)==gpar(b) && d[i][j]==-1) d[i][j]=w;
        }
    }
    for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(d[i][j]==-1) d[i][j]=mod;
    for(int i=0,a,b;i<m;i++){
        cin>>a>>b; b--; a*=2;
        for(int j=0;j<4; ++j)if(a<=d[b][j]) cout<<j+1;
        cout<<'\n';
    }
	
	return 0;
}

Compilation message (stderr)

park.cpp:74:58: warning: overflow in implicit constant conversion [-Woverflow]
 const ll maxn=2e3+10, maxm=1e3+10, lg=20, mod=1e9+7, inf=1e18;
                                                          ^~~~

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