Submission #1232220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232220		alexander707070	Toy (CEOI24_toy)	C++20	100 / 100	443 ms	287440 KiB

Main

#include <bits/stdc++.h>
#define MAXN 1507
using namespace std;

int n,m,rows,cols;
int lx,ly,ux,uy;
int sx,sy,ex,ey;

char t[MAXN][MAXN];

int fromy[MAXN][MAXN],toy[MAXN][MAXN];
int fromx[MAXN][MAXN],tox[MAXN][MAXN];

int pr[MAXN][MAXN],nxt[MAXN][MAXN];
bool block[MAXN][MAXN];

vector<int> g[MAXN*MAXN];
bool vis[MAXN*MAXN];

void calc_states(){
    for(int i=1;i<=n;i++){
        int last=0;

        for(int f=1;f<=m;f++){
            if(t[i][f]=='X')last=f;
            pr[i][f]=last;
        }

        last=m+1;
        for(int f=m;f>=1;f--){
            if(t[i][f]=='X')last=f;
            nxt[i][f]=last;
        }

        for(int f=1;f<=m;f++){
            if(t[i][f]=='X')continue;

            if(nxt[i][f]-pr[i][f]-1<cols)block[i][f]=true;
            else{
                fromy[i][f]=max(pr[i][f]+1,f-cols+1);
                toy[i][f]=min(nxt[i][f]-cols,f);
            }
        }
    }

    for(int f=1;f<=m;f++){
        int last=0;

        for(int i=1;i<=n;i++){
            if(t[i][f]=='X')last=i;
            pr[i][f]=last;
        }

        last=n+1;
        for(int i=n;i>=1;i--){
            if(t[i][f]=='X')last=i;
            nxt[i][f]=last;
        }

        for(int i=1;i<=n;i++){
            if(t[i][f]=='X')continue;

            if(nxt[i][f]-pr[i][f]-1<rows)block[i][f]=true;
            else{
                fromx[i][f]=max(pr[i][f]+1,i-rows+1);
                tox[i][f]=min(nxt[i][f]-rows,i);
            }
        }
    }
}

bool ok(int a,int b,int c,int d){
    if(b<c or d<a)return false;
    return true;
}

void build_graph(){
    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            if(block[i][f])continue;

            if(!block[i][f+1] and ok(fromx[i][f],tox[i][f],fromx[i][f+1],tox[i][f+1])){
                g[i*m+f].push_back(i*m+f+1);
                g[i*m+f+1].push_back(i*m+f);

            }

            if(!block[i+1][f] and ok(fromy[i][f],toy[i][f],fromy[i+1][f],toy[i+1][f])){
                g[i*m+f].push_back((i+1)*m+f);
                g[(i+1)*m+f].push_back(i*m+f);
            }
        }
    }
}

bool dfs(int x,int y){
    if(x==y)return true;
    vis[x]=true;

    for(int i:g[x]){
        if(vis[i])continue;
        if(dfs(i,y))return true;
    }

    return false;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>m>>n>>cols>>rows;
    cin>>lx>>ly>>ux>>uy;

    lx++; ly++; ux++; uy++;
    sx=ly; sy=ux;
    
    for(int i=1;i<=n;i++){
        for(int f=1;f<=m;f++){
            cin>>t[i][f];

            if(t[i][f]=='X')block[i][f]=true;

            if(t[i][f]=='*'){
                ex=i; ey=f;
            }
        }
    }

    calc_states();
    build_graph();

    if(dfs(sx*m+sy,ex*m+ey)){
        cout<<"YES\n";
    }else{
        cout<<"NO\n";
    }

    return 0;
}

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