oj.uz

Submission #83032

# Submission time Handle Problem Language Result Execution time Memory
83032 2018-11-04T08:44:08 Z FedericoS Park (BOI16_park) C++14
0 / 100
 851 ms 69556 KB 
#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];
		R[i]*=2;
	}
	for(int i=0;i<M;i++){
		cin>>V[i].first>>E[i];
		V[i].second=i;
	}
	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+1e-4<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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 69400 KB Output is correct
2 Incorrect 851 ms 69556 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 69556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 69400 KB Output is correct
2 Incorrect 851 ms 69556 KB Output isn't correct
3 Halted 0 ms 0 KB -