Submission #377947

#	Time	Username	Problem	Language	Result	Execution time	Memory
377947		YJU	Park (BOI16_park)	C++14	100 / 100	1189 ms	138696 KiB

park

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=1e5+10;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
const ld eps=1e-12;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
#define SQ(_a) ((_a)*(_a))

ll sz[N],dir[N];

ll find(ll nd){
	return (dir[nd]==nd?nd:dir[nd]=find(dir[nd]));
}

void Union(ll nda,ll ndb){
	nda=find(nda);ndb=find(ndb);
	if(nda==ndb)return ;
	if(sz[nda]>sz[ndb])swap(nda,ndb);
	sz[ndb]+=sz[nda];
	dir[nda]=ndb;
}

bool is(ll nda,ll ndb){
	return (find(nda)==find(ndb));
}

ll tx[N],ty[N],tr[N];
ll ans[N],qe[N],qr[N];
ll m,W,H,n;
ll side[100][20];
ll ve[40],ho[40];
vector<pair<ld,pll> > query,event;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	//prepare
	REP1(i,N-1)dir[i]=i,sz[i]=1;
	side[0][0]=n+4,side[0][1]=n+3;
	side[1][0]=n+3;side[1][1]=n+2;
	side[2][0]=n+2;side[2][1]=n+1;
	side[3][0]=n+1;side[3][1]=n+4;
	ho[0]=ho[1]=(1<<2)|(1<<3);
	ho[2]=ho[3]=(1<<1)|(1<<0);
	ve[0]=ve[3]=(1<<2)|(1<<1);
	ve[1]=ve[2]=(1<<0)|(1<<3);
	//endprepare
	cin>>W>>H;
	/*
			n+1
		-------------
		|3		   2|
	n+4	|0    	   1|n+2
		-------------
			n+3
	*/
	REP1(i,n){
		cin>>tx[i]>>ty[i]>>tr[i];
	}
	REP1(i,n)REP1(j,n){
		event.pb(mp((ld)sqrt((tx[i]-tx[j])*(tx[i]-tx[j])+(ty[i]-ty[j])*(ty[i]-ty[j]))-tr[i]-tr[j],mp(i,j)));
	}
	REP1(i,n){
		event.pb(mp(ty[i]-tr[i],mp(i,n+3)));
		event.pb(mp(H-ty[i]-tr[i],mp(i,n+1)));
		event.pb(mp(tx[i]-tr[i],mp(i,n+4)));
		event.pb(mp(W-tx[i]-tr[i],mp(i,n+2)));
	}
	REP1(i,m){
        cin>>qr[i]>>qe[i];
        query.pb(mp(2*qr[i],mp(qe[i],i)));
	}
	sort(event.begin(),event.end());
	sort(query.begin(),query.end());
	for(int i=0,j=0;i<SZ(query);i++){
        while(j<SZ(event)&&event[j].X<query[i].X){
			Union(event[j].Y.X,event[j].Y.Y);
			++j;
        }
        ll ent=query[i].Y.X-1,id=query[i].Y.Y;
        if(is(n+2,n+4)){
			ans[id]|=ho[ent];
        }
        if(is(n+1,n+3)){
			ans[id]|=ve[ent];
        }
        if(is(side[ent][0],side[ent][1])){
			ans[id]|=(((1<<4)-1)^(1<<ent));
        }
        REP(j,4){
			if(j==ent)continue;
			if(is(side[j][0],side[j][1])){
				ans[id]|=(1<<j);
			}
        }
	}
	REP1(i,m){
		REP(j,4)if(((ans[i]>>j)&1)==0)cout<<j+1;
		cout<<"\n";
	}
	return 0;
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1

*/

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