Submission #159566

#	Time	Username	Problem	Language	Result	Execution time	Memory
159566		theknife2001	Konj (COCI19_konj)	C++17	70 / 70	76 ms	4216 KiB

konj

#include <bits/stdc++.h>

using namespace std;
const int N=305;
const int M=2e5+55;
char ans[N][N];
int s[N][N];
int par[M];

int find_par(int u)
{
	if(u==par[u])
	return u;
	par[u]=find_par(par[u]);
	return par[u];
}

void merge(int u , int v)
{
	u=find_par(u);
	v=find_par(v);
	if(u==v)
	return ;
	par[v]=u;
}
	

int main()
{
  	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=0;i<=n;i++)
	par[i]=i;
	int a,b,c,d;
	for(int k=1;k<=n;k++)
	{
		cin>>a>>b>>c>>d;
		b=N-b-3;
		d=N-d-3;
		for(int i=min(d,b);i<=max(b,d);i++)
		{
			for(int j=min(a,c);j<=max(a,c);j++)
			{
				if(s[i][j]==0)
				s[i][j]=k;
				else
				merge(s[i][j],k);
			}
		}
	}
	int x,y;
	cin>>y>>x;
	x=N-x-3;
	if(s[x][y]==0)
	return 0;
	int t=find_par(s[x][y]);
	int mni,mnj,mxi,mxj;
	mni=mnj=M;
	mxi=mxj=0;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			if(find_par(s[i][j])==t&&s[i][j]!=0)
			{
				ans[i][j]='#';
				mni=min(mni,i);
				mnj=min(mnj,j);
				mxi=max(mxi,i);
				mxj=max(mxj,j);
			}
			else
			ans[i][j]='.';
		}
	}
	for(int i=mni;i<=mxi;i++)
	{
		for(int j=mnj;j<=mxj;j++)
		{
			cout<<ans[i][j];
		}
		cout<<endl;
	}
	
	
	return 0;
}

• Subtask 1: 70 / 70