Submission #1075627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075627		anton	Toy (CEOI24_toy)	C++17	100 / 100	753 ms	400064 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

int W, H, K, L;

const int MAX_N = 2500;

int dist_dir[4][MAX_N][MAX_N];
char cont[MAX_N][MAX_N];
struct Grid{
    int a, b;
    vector<vector<pii>> true_name;

    Grid(int _a, int _b){
        a= _a;
        b= _b;
        true_name.resize(a, vector<pii>(b));
        for(int i = 0; i<a; i++){
            for(int j = 0; j<b;j++){
                true_name[i][j] = {i, j};
            }
        }
    }
    Grid flip(){
        Grid res(b, a);
        for(int i = 0; i<a; i++){
            for(int j = 0; j<b; j++){
                res.true_name[j][a-i-1] = true_name[i][j];
            }
        }
        return res;
    }

    void calc_dist(int dir_id){
        for(int i = 0; i<a; i++){
            int streak= 0;
            for(int j = 0; j<b; j++){
                pii real = true_name[i][j];
                if(cont[real.first][real.second] == 'X'){
                   streak = 0; 
                }
                else{
                    streak++;
                }
                dist_dir[dir_id][real.first][real.second] = streak;
            }
        }
    }
};


int get_inter_len(pii a, pii b, int dir){
    int res = min(dist_dir[dir][a.first][a.second], dist_dir[dir][b.first][b.second]) + min(dist_dir[dir+2][a.first][a.second], dist_dir[dir+2][b.first][b.second])-1;
    return res;
}
vector<pii> get_adj(pii pos){
    
    vector<pii> res;
    if(pos.first>0){
        pii other = {pos.first-1, pos.second};
        if(get_inter_len(pos, other, 0)>=K){
            res.push_back(other);
        }
    }
    if(pos.first<H-1){
        pii other = {pos.first+1, pos.second};
        if(get_inter_len(pos, other, 0)>=K){
            res.push_back(other);
        }
    }
    if(pos.second>0){
        pii other = {pos.first, pos.second-1};
        if(get_inter_len(pos, other, 1)>=L){
            res.push_back(other);
        }
    }
    if(pos.second<W-1){
        pii other = {pos.first, pos.second+1};
        if(get_inter_len(pos, other, 1)>=L){
            res.push_back(other);
        }
    }


    return res;
}

bool dfs(vector<vector<bool>>& vis, pii cur_pos){
    vis[cur_pos.first][cur_pos.second] = true;

    if(cont[cur_pos.first][cur_pos.second] == '*'){
        return true;
    }

    for(auto e: get_adj(cur_pos)){
        if(!vis[e.first][e.second]){
            if(dfs(vis, e)){
                return true;
            }
        }
    }
    return false;
}
signed main(){
    cin>>W>>H>>K>>L;

    pii h, v;
    cin>>h.second>>h.first>>v.second>>v.first;

    pii init_pos = {h.first, v.second};
    Grid grid(H, W);
    for(int i = 0; i<H; i++){
        for(int j = 0; j<W; j++){
            cin>>cont[i][j];
        }
    }


    for(int k= 0; k<4; k++){
        grid.calc_dist(k);
        grid = grid.flip();
    }

    vector<vector<bool>> vis(H, vector<bool>(W));

    if(dfs(vis, init_pos)){
        cout<<"YES"<<endl;
        return 0;
    }
    else{
        cout<<"NO"<<endl;
        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