oj.uz

Submission #739087

# Submission time Handle Problem Language Result Execution time Memory
739087 2023-05-09T23:25:14 Z Morley Park (BOI16_park) C++14
0 / 100
 152 ms 64568 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 64568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

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

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 152 ms 64568 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -