Submission #83034

#	Time	Username	Problem	Language	Result	Execution time	Memory
83034		FedericoS	Park (BOI16_park)	C++14	100 / 100	1052 ms	87604 KiB

park

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long double ld;
typedef pair<ld,ld> pdd;

int N,M;
ld W,H;
pdd T[2005];
ld R[2005];
pair<ld,int> V[100005];
int E[100005];
int P[2020],S[2020];
vector<pair<pair<int,int>,ld>> Q;
string ans[100005];

bool comp(pair<pair<int,int>,ld> a, pair<pair<int,int>,ld> b){
	return a.second>b.second;
}

int fi(int a){
	while(a!=P[a])
		a=P[a];
	return a;
}

bool fi(int a, int b){
	return(fi(a)!=fi(b));
}

void un(int a, int b){

	//cout<<"un "<<a<<" "<<b<<endl;

	a=fi(a);
	b=fi(b);

	if(a==b)
		return;

	if(S[a]<S[b])
		swap(a,b);

	P[b]=a;
	S[a]=max(S[a],S[b]+1);

}

bool raggiungibile(int a, int b){

	if(a==b)
		return true;

	bool flag=true;

	if(a==0 or b==0)
		flag&=fi(N+2,N+3);
	if(a==1 or b==1)
		flag&=fi(N+2,N+1);
	if(a==2 or b==2)
		flag&=fi(N+1,N);
	if(a==3 or b==3)
		flag&=fi(N,N+3);

	if((a==0 or a==3) and (b==1 or b==2))
		flag&=fi(N,N+2);
	if((b==0 or b==3) and (a==1 or a==2))
		flag&=fi(N,N+2);

	if((a==0 or a==1) and (b==2 or b==3))
		flag&=fi(N+1,N+3);
	if((b==0 or b==1) and (a==2 or a==3))
		flag&=fi(N+1,N+3);

	return flag;

}

int main(){
	cin>>N>>M;
	cin>>W>>H;
	for(int i=0;i<N;i++)
		cin>>T[i].first>>T[i].second>>R[i];
	for(int i=0;i<M;i++){
		cin>>V[i].first>>E[i];
		V[i].second=i;
		V[i].first*=2;
	}
	sort(V,V+M);

	for(int i=0;i<N+4;i++)
		P[i]=i;

	for(int i=0;i<N;i++){
		Q.push_back({{i,N},H-T[i].second-R[i]});
		Q.push_back({{i,N+1},W-T[i].first-R[i]});
		Q.push_back({{i,N+2},T[i].second-R[i]});
		Q.push_back({{i,N+3},T[i].first-R[i]});
		for(int j=i+1;j<N;j++)
			Q.push_back({{i,j},sqrt((T[i].first-T[j].first)*(T[i].first-T[j].first)+(T[i].second-T[j].second)*(T[i].second-T[j].second))-R[i]-R[j]});
	}

	sort(Q.begin(),Q.end(),comp);

	//for(auto p:Q)cout<<p.first.first<<" "<<p.first.second<<" "<<p.second<<endl;

	for(int j=0;j<M;j++){

		auto v=V[j];

		//cout<<v.second<<endl;

		while(!Q.empty() and Q.back().second<v.first){
			un(Q.back().first.first,Q.back().first.second);
			Q.pop_back();
		}

		for(int i=0;i<4;i++)
			if(raggiungibile(E[v.second]-1,i))
				ans[v.second]+=(char)(i+(int)'1');
	}

	for(int i=0;i<M;i++)
		cout<<ans[i]<<"\n";

}

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