Submission #739087

#	Time	Username	Problem	Language	Result	Execution time	Memory
739087		Morley	Park (BOI16_park)	C++14	0 / 100	152 ms	64568 KiB

park

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

int inf = 1000000000;

vector<int> par;

int fi(int i) {
	if(par[i]==par[par[i]]) return par[i];
	par[i]=fi(par[i]);
	return par[i];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n,m,w,h; cin>>n>>m>>w>>h;
	priority_queue<pair<long long,pair<int,int>>> PQ;
	vector<long long> X(n),Y(n),R(n),E(m);
	for(int i=0;i<n;i++) cin>>X[i]>>Y[i]>>R[i];
	for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) {
		long long d=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]))-R[i]-R[j];
		PQ.push(make_pair(-d,make_pair(i,j)));
	}
	for(int j=0;j<m;j++) {
		long long r,e; cin>>r>>e; PQ.push(make_pair(-2*r,make_pair(inf,j))); E[j]=e;
	}
	for(int i=0;i<n;i++) {
		PQ.push(make_pair(-Y[i]+R[i],make_pair(i,n+2)));
		PQ.push(make_pair(-w+X[i]+R[i],make_pair(i,n+1)));
		PQ.push(make_pair(-h+Y[i]+R[i],make_pair(i,n)));
		PQ.push(make_pair(-X[i]+R[i],make_pair(i,n+3)));
	}
	for(int i=0;i<n+4;i++) par.push_back(i);
	vector<string> S(m);
	while(!PQ.empty()) {
		auto p=PQ.top(); PQ.pop();
		int i=p.second.first, j=p.second.second;
		if(i!=inf && fi(j)!=fi(i)) {
			par[fi(j)]=fi(i);
			//cout<<"merged "<<i<<" with "<<j<<"\n";
		}
		else {
			if(E[j]==1) {
				if(fi(n+2)==fi(n+3)) S[j]="1\n";
				else if(fi(n+1)==fi(n+3)) S[j]="12\n";
				else if(fi(n)==fi(n+2)) S[j]="14\n";
                else if(fi(n)==fi(n+3) && fi(n+1)==fi(n+2)) S[j]="13\n";
				else if(fi(n+3)==fi(n)) S[j]="123\n";
				else if(fi(n)==fi(n+1)) S[j]="124\n";
				else if(fi(n+1)==fi(n+2)) S[j]="134\n";
				else S[j]="1234\n";
			}
			else if(E[j]==2) {
				if(fi(n+1)==fi(n+2)) S[j]="2\n";
				else if(fi(n+1)==fi(n+3)) S[j]="12\n";
				else if(fi(n)==fi(n+2)) S[j]="23\n";
                else if(fi(n)==fi(n+1) && fi(n+2)==fi(n+3)) S[j]="24\n";
				else if(fi(n+3)==fi(n)) S[j]="123\n";
				else if(fi(n)==fi(n+1)) S[j]="124\n";
				else if(fi(n+2)==fi(n+3)) S[j]="234\n";
				else S[j]="1234\n";
			}
			else if(E[j]==3) {
				if(fi(n)==fi(n+1)) S[j]="3\n";
				else if(fi(n+1)==fi(n+3)) S[j]="34\n";
				else if(fi(n)==fi(n+2)) S[j]="23\n";
                else if(fi(n)==fi(n+3) && fi(n+1)==fi(n+2)) S[j]="13\n";
				else if(fi(n+3)==fi(n)) S[j]="123\n";
				else if(fi(n+2)==fi(n+3)) S[j]="234\n";
				else if(fi(n+1)==fi(n+2)) S[j]="134\n";
				else S[j]="1234\n";
			}
			else if(E[j]==4) {
				if(fi(n)==fi(n+3)) S[j]="4\n";
				else if(fi(n+1)==fi(n+3)) S[j]="34\n";
				else if(fi(n)==fi(n+2)) S[j]="14\n";
                else if(fi(n)==fi(n+1) && fi(n+2)==fi(n+3)) S[j]="24\n";
				else if(fi(n+3)==fi(n+2)) S[j]="234\n";
				else if(fi(n)==fi(n+1)) S[j]="124\n";
				else if(fi(n+1)==fi(n+2)) S[j]="134\n";
				else S[j]="1234\n";
			}
			//(n+k)<<" "; cout<<"\n//for(int k=0;k<4;k++) cout<<fi";
		}
	}

	for(int j=0;j<m;j++) cout<<S[j];

	return 0;
}

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