Submission #1293017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293017		dosts	Toy (CEOI24_toy)	C++20	100 / 100	284 ms	179516 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e18;

const int N = 1e5+1;

void solve() {
    int n,m,a,b;
    cin >> m >> n >> b >> a;
    string grid[n+1];
    int sx,sy,tx=-1,ty=-1;
    int cx,cy,dx,dy;
    cin >> dy >> dx >> cy >> cx ;
    for (int j = 0;j<b;j++) {
        for (int jj = 0;jj<a;jj++) {
            if (pii{cx+jj,cy} == pii{dx,dy+j}) {
                sx = cx+jj,sy = cy;
            }
        }
    }
    for (int i=1;i<=n;i++) {
        cin >> grid[i];
        for (int j = 0;j<m;j++) {
            if (grid[i][j] == '*') {
                tx = i,ty = j+1;
            }
        }
    }
    sx++,sy++;
    auto get = [&](vector<vi>& pr,int x1,int y1,int x2,int y2) -> int {
        if (x1 > x2 || y1 > y2) return 0;
        return pr[x2][y2]-pr[x1-1][y2]-pr[x2][y1-1]+pr[x1-1][y1-1];
    };

    vector<vi> pref(n+1,vi(m+1,0));
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=m;j++) {
            pref[i][j] = pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(grid[i][j-1]=='X');
        }
    }
    vector<vi> sftle(n+1,vi(m+1,0)),sftri(n+1,vi(m+1,0)),sftdn(n+1,vi(m+1,0)),sftup(n+1,vi(m+1,0));
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=m;j++) {
            if (i < a || j == 1) continue;
            sftle[i][j] = !get(pref,i-a+1,j-1,i,j);
        }
    }
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=m;j++) {
            if (i < a || j == m) continue;
            sftri[i][j] = !get(pref,i-a+1,j,i,j+1);
        }
    }
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=m;j++) {
            if (i == n || j < b) continue;
            sftdn[i][j] = !get(pref,i,j-b+1,i+1,j);
        }
    }
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=m;j++) {
            if (i == 1 || j < b) continue;
            sftup[i][j] = !get(pref,i-1,j-b+1,i,j);
        }
    }
    
    for (int i=1;i<=n;i++) {
        for (int j = 1;j<=m;j++) {
            sftle[i][j] = sftle[i-1][j]+sftle[i][j-1]-sftle[i-1][j-1]+(sftle[i][j]);
            sftri[i][j] = sftri[i-1][j]+sftri[i][j-1]-sftri[i-1][j-1]+(sftri[i][j]);
            sftdn[i][j] = sftdn[i-1][j]+sftdn[i][j-1]-sftdn[i-1][j-1]+(sftdn[i][j]);
            sftup[i][j] = sftup[i-1][j]+sftup[i][j-1]-sftup[i-1][j-1]+(sftup[i][j]);
        }
    }
    
    vector<vi> dist(n+1,vi(m+1,inf));
    int yuk[n+1][m+1],asa[n+1][m+1],sa[n+1][m+1],so[n+1][m+1];
    int lst = 0;
    for (int i=1;i<=n;i++){
        lst = 0;
        for (int j = 1;j<=m;j++) {
            if (grid[i][j-1] == 'X') {
                lst = j;
                continue;
            }
            so[i][j] = lst;
        }
        lst = m+1;
        for (int j = m;j>=1;j--) {
            if (grid[i][j-1] == 'X') {
                lst = j;
                continue;
            }
            sa[i][j] = lst;
        }
    }
    for (int j=1;j<=m;j++) {
        lst = 0;
        for (int i=1;i<=n;i++) {
            if (grid[i][j-1] == 'X') {
                lst = i;
                continue;
            }
            yuk[i][j] = lst;
        }
        lst = n+1;
        for (int i = n;i>=1;i--) {
            if (grid[i][j-1] == 'X') {
                lst = i;
                continue;
            }
            asa[i][j] = lst;
        }
    }
    dist[sx][sy] = 0;   
    queue<pii> q;
    q.push({sx,sy});
    
    auto cool = [&](int x,int y) -> bool {
        return (x >= 1 && x <= n && y >= 1 && y <= m) && dist[x][y] == inf && grid[x][y-1]!='X';
    };

    while (!q.empty()) {
        pii f = q.front();
        q.pop();
        int x = f.ff,y = f.ss;
        int upp = max(x,yuk[x][y]-a);
        int dwn = min(x+a-1,asa[x][y]-1);
        int sag = min(y+b-1,sa[x][y]-1);
        int sol = max(y,so[x][y]+b);
        if (cool(x,y-1) && get(sftle,upp,y,dwn,y)) {
            dist[x][y-1] = dist[x][y]+1;
            q.push({x,y-1});
        }
        if (cool(x,y+1) && get(sftri,upp,y,dwn,y)) {
            dist[x][y+1] = dist[x][y]+1;
            q.push({x,y+1});
        }
        if (cool(x-1,y) && get(sftup,x,sol,x,sag)) {
            dist[x-1][y] = dist[x][y]+1;
            q.push({x-1,y});
        }       
        if (cool(x+1,y) && get(sftdn,x,sol,x,sag)) {
            dist[x+1][y] = dist[x][y]+1;
            q.push({x+1,y});
        }
    }
    if (dist[tx][ty] == inf) cout << "NO\n";
    else cout << "YES\n"; 
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27