Submission #377927

#	Time	Username	Problem	Language	Result	Execution time	Memory
377927		YJU	Park (BOI16_park)	C++14	0 / 100	531 ms	66376 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=2e6+5;
const ll MOD=1e9+7;
const ld pi=3.14159265359;
const ll INF=(1LL<<60);
const ld eps=1e-14;
#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 n,m,W,H;
ll side[4][2];
ll ve[4],ho[4];
vector<pair<ld,pll> > query,event;

ld dis(ll ida,ll idb){
	return sqrt(SQ(tx[ida]-tx[idb])+SQ(ty[ida]-ty[idb]));
}

int main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	//prepare
	REP1(i,n+4)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]=15-3;
	ho[2]=ho[3]=3;
	ve[0]=ve[3]=6;
	ve[1]=ve[2]=15-6;
	//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,i-1){
		event.pb(mp(dis(i,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(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-eps<2*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);
        }
	}
	REP1(i,m){
		REP(j,4)if(!((ans[i]>>j)&1))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: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42