Submission #735314

#	Time	Username	Problem	Language	Result	Execution time	Memory
735314		Username_taken12	Park (BOI16_park)	C++17	0 / 100	2565 ms	110504 KiB

park

#include <bits/stdc++.h>
#include <string>
#include <ext/pb_ds/assoc_container.hpp>
// Including tree_order_statistics_node_update
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vii = vector<vector<int>>;
using ll = long long;
using vl = vector<ll>;
using vll = vector<vector<ll>>;
#define pb push_back
#define mp make_pair
#define s second
#define f first
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


class DSU{
	public:
		vi parents;
		vi sizes;
		//vector<vector<boolean>> status;

		DSU(int size)
		{
			vi temp(size+4);
			parents=temp;
			//vector<vector<boolean>> temp2(size);
			//status=temp2;
			vi temp2(size+4);

			for(int i=0; i<size+4; i++)
			{
				parents[i]=-1;
				temp2[i]=1;
			}
			sizes=temp2;
		}

		int find(int x)
		{
			if(parents[x]==-1)
				return x;
			parents[x]=find(parents[x]);
			return parents[x];
		}

		bool join(int x, int y)
		{
			//cout<<"JOIN "<<x<<' '<<y<<endl;
			x=find(x);
			y=find(y);
			if(x==y)
				return false;
			
			if(sizes[x]<sizes[y])
			{
				int z=x;
				x=y; y=z;
			}

			parents[y]=x;
			sizes[x]+=sizes[y];
			return true;
		}

		bool connected(int x, int y)
		{
			//cout<<x<<' '<<y<<endl;
			return find(x)==find(y);
		}
};

string print(vi item)
{
	for(int i=0; i<item.size(); i++)
		cout<<item[i]<<' ';
	return "";
}

int main() {
	int n, m; cin>>n>>m;

	int w, h; cin>>w>>h;

	vi temp(3);
	vector<vector<int>> trees(n, temp);
	for(int i=0; i<n; i++)
		cin>>trees[i][2]>>trees[i][0]>>trees[i][1];

	vector<vi> visitors(m, temp); //radius, 1, entrance, i
	for(int i=0; i<m; i++){
		cin>>visitors[i][0]>>visitors[i][2];
		visitors[i][3]=i; visitors[i][1]=1;
	}

	priority_queue<vi> que; //radius, type, (entrance, i)/(a, b)

	for(int i=0; i<n; i++)
		for(int j=i+1; j<n; j++)
		{
			vi entry(4);
			entry[0]=-1*((trees[i][0]-trees[j][0])*(trees[i][0]-trees[j][0])
			+(trees[i][1]-trees[j][1])*(trees[i][1]-trees[j][1])
			-(trees[i][2]+trees[j][2])*(trees[i][2]+trees[j][2]));
			entry[1]=0;
			entry[2]=i;
			entry[3]=j;
			que.push(entry);
		}
	for(int i=0; i<n; i++) //top = 0, right = 1, down = 2, left = 3
	{
		vi entry(4);
		entry[0]=-1*((h-trees[i][1]-trees[i][2])*(h-trees[i][1]-trees[i][2]));
		entry[1]=0;
		entry[2]=i;
		entry[3]=n;
		que.push(entry);

		entry[0]=-1*(w-trees[i][0]-trees[i][2])*(w-trees[i][0]-trees[i][2]);
		entry[3]=n+1;
		que.push(entry);

		entry[0]=-1*(trees[i][1]-trees[i][2])*(trees[i][1]-trees[i][2]);
		entry[3]=n+2;
		que.push(entry);

		entry[0]=-1*(trees[i][0]-trees[i][2])*(trees[i][0]-trees[i][2]);
		entry[3]=n+3;
		que.push(entry);
	}

	for(int i=0; i<m; i++)
	{
		vi entry(4);
		entry[0]=-1*visitors[i][0]*visitors[i][0]*4;
		entry[1]=visitors[i][1];
		entry[2]=visitors[i][2];
		entry[3]=visitors[i][3];
		que.push(entry);
	}
	for(int i=0; i<4; i++)
		trees.pb(vi{n+i});
	vi sol(m);
	DSU dsu(n+4);

	vector<bool> vb(4);
	vector<vector<bool>> match(4, vb);
	
	for(int i=0; i<4; i++)
		for(int j=0; j<4; j++)
			match[i][j]=true;
	vector<vector<bool>> dead(4, vb);
	for(int i=0; i<4; i++)
		dead[i][i]=true;
	
	
	/*while(que.size()>0){
		vi it = que.top();
		que.pop();
		cout<<it[0]<<' '<<it[1]<<' '<<it[2]<<' '<<it[3]<<endl;
	}*/

	while(que.size()>0)
	{
		vi it = que.top();
		que.pop();

		if(it[1]==0){
			//cout<<"Started 0:"<<endl;
			//cout<<print(it)<<endl;
			//cout<<print(trees[it[2]])<<" | "<<print(trees[it[3]])<<endl;
			dsu.join(it[2], it[3]);
			if(dsu.connected(n+0,n+2))
			{
				vector<vector<bool>> held=match;
				match=dead;
				match[0][3]=held[0][3]; 
				match[1][2]=held[1][2];
			}
			if(dsu.connected(n+1,n+3))
			{
				vector<vector<bool>> held=match;
				match=dead;
				match[2][3]=held[2][3]; 
				match[0][1]=held[0][1];
			}
			if(dsu.connected(n+0,n+1)) //3
			{
				for(int i=0; i<4; i++)
				{
					if(i==2)
						continue;
					match[min(i,2)][max(i,2)]=false;
				}
			}
			if(dsu.connected(n+1,n+2)) //2
			{
				for(int i=0; i<4; i++)
				{
					if(i==1)
						continue;
					match[min(i,1)][max(i,1)]=false;
				}
			}
			if(dsu.connected(n+2,n+3)) //1
			{
				for(int i=0; i<4; i++)
				{
					if(i==0)
						continue;
					match[min(i,0)][max(i,0)]=false;
				}
			}
			if(dsu.connected(n+3,n+0)) //4
			{
				for(int i=0; i<4; i++)
				{
					if(i==3)
						continue;
					match[min(i,3)][max(i,3)]=false;
				}
			}
			/*for(int i=0; i<4; i++){
				for(int j=i; j<4; j++)
					cout<<match[i][j]<<' ';
				cout<<endl;
			}
			cout<<"Finished"<<endl;*/
		}
		if(it[1]==1) //top = 0, right = 1, bottom = 2, left = 3
		{
			//cout<<"Started 1 :" <<endl;
			/*for(int i=0; i<4; i++){
				for(int j=i; j<4; j++)
					cout<<match[i][j]<<' ';
				cout<<endl;
			}*/
			int enter=it[2]-1;
			int out=0;
			for(int i=0; i<4; i++)
				if(match[min(enter, i)][max(enter, i)])
					out=out*10+(i+1);
			sol[it[3]]=out;
			//cout<<"Finished"<<endl;
		}

	}

	for(int i=0; i<m; i++)
		cout<<sol[i]<<'\n';
	cout<<endl;
}

Compilation message (stderr)

park.cpp: In function 'std::string print(vi)':
park.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0; i<item.size(); i++)
      |               ~^~~~~~~~~~~~

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