Submission #925646

#	Time	Username	Problem	Language	Result	Execution time	Memory
925646		pcc	Park (BOI16_park)	C++17	100 / 100	726 ms	51960 KiB

park

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 2024;

inline ll sq(ll k){return k*k;}

struct C{
	ll x,y,r;
	C(){}
	C(ll xx,ll yy,ll rr):x(xx),y(yy),r(rr){}
};

struct DSU{
	int dsu[mxn],sz[mxn];
	DSU(){
		for(int i = 0;i<mxn;i++)dsu[i] = i,sz[i] = 1;
	}
	void init(){
		for(int i = 0;i<mxn;i++)dsu[i] = i,sz[i] = 1;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		sz[a] += sz[b];
		dsu[b] = a;
		return;
	}
};

int N,Q;
ll H,W;
C arr[mxn];
vector<pair<ll,pll>> v;
ll neck[5][5];
vector<pii> req[5][5];
bool done[5][5];
DSU dsu;

inline void getr(int a,int b,ll R){
	ll l = 0,r = min(H,W);
	while(l != r){
		ll mid = (l+r+1)>>1;
		if(sq(mid+arr[a].r+arr[b].r)<=R)l = mid;
		else r = mid-1;
	}
	//cout<<a<<' '<<b<<":"<<R<<' '<<l<<endl;
	v.push_back(make_pair(l,make_pair(a,b)));
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q>>W>>H;
	for(int i = 1;i<=N;i++){
		cin>>arr[i].x>>arr[i].y>>arr[i].r;
	}
	for(int i = 1;i<=N;i++){
		for(int j = i+1;j<=N;j++){
			getr(i,j,sq(arr[i].x-arr[j].x)+sq(arr[i].y-arr[j].y));
		}
		getr(i,N+1,sq(arr[i].x));
		getr(i,N+2,sq(H-arr[i].y));
		getr(i,N+3,sq(W-arr[i].x));
		getr(i,N+4,sq(arr[i].y));
	}
	getr(N+1,N+3,sq(W));
	getr(N+2,N+4,sq(H));
	sort(v.begin(),v.end());
	req[1][2] = {{2,4},{3,4},{1,4}};
	req[1][3] = {{2,4},{1,4},{1,3},{2,3}};
	req[1][4] = {{1,3},{1,2},{1,4}};
	req[2][3] = {{1,3},{2,3},{3,4}};
	req[2][4] = {{1,3},{2,4},{1,2},{3,4}};
	req[3][4] = {{2,4},{1,2},{2,3}};
	for(int i = 1;i<=4;i++)neck[i][i] = min(H,W);
	//cout<<endl;
	for(auto &now:v){
		//cout<<now.fs<<' '<<now.sc.fs<<' '<<now.sc.sc<<endl;
		dsu.onion(now.sc.fs,now.sc.sc);
		for(int i = 1;i<=4;i++){
			for(int j = i+1;j<=4;j++){
				bool flag = true;
				for(auto &k:req[i][j]){
					if(dsu.root(N+k.fs) == dsu.root(N+k.sc))flag = false;
				}
				if(!done[i][j])neck[j][i] = neck[i][j] = now.fs;
				if(!flag)done[i][j] = true;
			}
		}
	}
	/*
	for(int i = 1;i<=4;i++){
		for(int j = 1;j<=4;j++)cout<<neck[i][j]<<' ';cout<<endl;
	}

   */
	while(Q--){
		ll n,r;
		cin>>r>>n;
		for(int i = 1;i<=4;i++){
			if(neck[n][i]>=r*2)cout<<i;
		}
		cout<<'\n';
	}
	return 0;
}

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