Submission #1050795

#TimeUsernameProblemLanguageResultExecution timeMemory
105079512345678Toy (CEOI24_toy)C++17
9 / 100
6 ms23228 KiB
#include <bits/stdc++.h> using namespace std; const int nx=1505; int n, k, l, r, c, dpl[nx][nx], dpr[nx][nx], dpup[nx][nx], dpdn[nx][nx], a, b, w, h, x, y, tmp; pair<int, int> dsu[nx][nx]; char mp[nx][nx]; pair<int, int> find(pair<int, int> loc) { if (dsu[loc.first][loc.second]==loc) return loc; return dsu[loc.first][loc.second]=find(dsu[loc.first][loc.second]); } int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>c>>r>>w>>h; cin>>tmp>>x>>tmp>>y; x++, y++; for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) cin>>mp[i][j], dsu[i][j]={i, j}; for (int i=1; i<=r; i++) for (int j=1; j<=c; j++) if (mp[i][j]=='*') a=i, b=j; //cout<<"debug "<<x<<' '<<y<<' '<<a<<' '<<b<<'\n'; for (int i=1; i<=r; i++) { for (int j=1; j<=c; j++) { if (mp[i][j]=='X') continue; if (j==1||mp[i][j-1]=='X') dpl[i][j]=j; else dpl[i][j]=dpl[i][j-1]; } } for (int i=1; i<=r; i++) { for (int j=c; j>=1; j--) { if (mp[i][j]=='X') continue; if (j==c||mp[i][j+1]=='X') dpr[i][j]=j; else dpr[i][j]=dpr[i][j+1]; } } for (int j=1; j<=c; j++) { for (int i=1; i<=r; i++) { if (mp[i][j]=='X') continue; if (i==1||mp[i-1][j]=='X') dpup[i][j]=i; else dpup[i][j]=dpup[i-1][j]; } } for (int j=1; j<=c; j++) { for (int i=r; i>=1; i--) { if (mp[i][j]=='X') continue; if (i==r||mp[i+1][j]=='X') dpdn[i][j]=i; else dpdn[i][j]=dpdn[i+1][j]; } } for (int i=1; i<=r; i++) { for (int j=1; j<c; j++) { if (mp[i][j]=='X'||mp[i][j+1]=='X'||dpdn[i][j]-dpup[i][j]+1<h||dpdn[i][j+1]-dpup[i][j+1]+1<h) continue; int st=min({dpdn[i][j], dpdn[i][j+1], i+h-1}); if (st-h+1>=dpup[i][j]&&st-h+1>=dpup[i][j+1]) { auto pu=find({i, j}), pv=find({i, j+1}); dsu[pu.first][pu.second]=pv; } } } for (int i=1; i<r; i++) { for (int j=1; j<=c; j++) { if (mp[i][j]=='X'||mp[i+1][j]=='X'||dpr[i][j]-dpl[i][j]+1<w||dpr[i+1][j]-dpl[i+1][j]+1<w) continue; int st=min({dpr[i][j], dpr[i+1][j], j+w-1}); if (st-w+1>=dpl[i][j]&&st-w+1>=dpl[i+1][j]) { auto pu=find({i, j}), pv=find({i+1, j}); dsu[pu.first][pu.second]=pv; } } } if (find({x, y})==find({a, b})) cout<<"YES"; else cout<<"NO"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...