Submission #1368143

#TimeUsernameProblemLanguageResultExecution timeMemory
1368143gvancakToy (CEOI24_toy)C++20
0 / 100
7 ms11868 KiB
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
const ll NN=3e6+5,N=1505,INF=1e12;
ll ans,n,m,k,l,par[NN],sz[NN],r_suf[N][N],r_pref[N][N],d[N][N],c_pref[N][N],c_suf[N][N],idx1,idx2,idx3,idx4,st,en,x,y;
char a[N][N];
int find_set(int u){
	if (par[u]==u) return u;
	return par[u]=find_set(par[u]);
}
void unite_set(int a,int b){
	a=find_set(a);
	b=find_set(b);
	if (a==b) return ;
	if (sz[a]<sz[b]) swap(a,b);
	sz[a]+=sz[b]; par[b]=a;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
   
    cin >> n >> m >> k >> l; swap(n,m);
    cin >> idx1 >> idx2 >> idx3 >> idx4;
    idx1=idx2+1;
    idx2=idx3+1;
    st=(idx1-1)*m+idx2;
    for (int i=1; i<=n; i++){
    	for (int j=1; j<=m; j++){
    		cin>> a[i][j];
		}
	}
	for (int i=1; i<=n*m; i++){
		par[i]=i; sz[i]=1;
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			if (a[i][j]=='X') r_pref[i][j]=j;
			else r_pref[i][j]=r_pref[i][j-1];
		}
		r_suf[i][m+1]=m+1;
		for (int j=m; j>=1; j--){
			if (a[i][j]=='X') r_suf[i][j]=j;
			else r_suf[i][j]=r_suf[i][j+1];
		}
	}
	
	for (int i=1; i<=m; i++){
		for (int j=1; j<=n; j++){
			if (a[j][i]=='X') c_pref[j][i]=j;
			else c_pref[j][i]=c_pref[j-1][i];
		}
		c_suf[n+1][i]=n+1;
		for (int j=n; j>=1; j--){
			if (a[j][i]=='X') c_suf[j][i]=j;
			else c_suf[j][i]=c_suf[j+1][i];
		}
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
			x=c_suf[i][j]-c_pref[i][j]-1;
			y=r_suf[i][j]-r_pref[i][j]-1;
			if (x>=l && y>=k) d[i][j]=1; else d[i][j]=0;
		}
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++){
		//	cout<<i<<" "<<j<<" "<<c_pref[i][j]<<" "<<c_suf[i][j]<<endl;
			if (a[i][j]=='*'){
				en=(i-1)*m+j;
			}
			if (d[i][j]==0) continue;
			// marjvniv
			if (j<m && d[i][j+1]==1){
				x=c_pref[i][j+1]; y=c_suf[i][j+1];
				if (y-x-1>=l){
					
					unite_set((i-1)*m+j,(i-1)*m+j+1);
				}
			}
			//marcxniv
			if (j>1 && d[i][j-1]==1){
				x=c_pref[i][j-1]; y=c_suf[i][j-1];
				if (y-x-1>=l){
					unite_set((i-1)*m+j,(i-1)*m+j-1);
				}
			}
			//qvevit
			if (i<n && d[i+1][j]==1){
				x=r_pref[i+1][j]; y=r_suf[i+1][j];
				if (y-x-1>=k){
					unite_set(i*m+j,(i-1)*m+j);
				}
			}
			//zevit
			if (i>1 && d[i-1][j]==1){
				x=r_pref[i-1][j]; y=r_suf[i-1][j];
				if (y-x-1>=k){
					unite_set((i-2)*m+j,(i-1)*m+j);
				}
			}
			
		}
	}
	x=find_set(st); y=find_set(en);
	if (x==y) cout<<"YES"<<endl; else cout<<"NO"<<endl;
	
	

}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...