Submission #1105017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105017		SalihSahin	Toy (CEOI24_toy)	C++14	100 / 100	206 ms	75924 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int mod = 1e9 + 7;
const int inf = 1e15;
const int N = 1e5+5;

bool intersect(pair<int, int> p1, pair<int, int> p2){
    return max(p1.first, p2.first) <= min(p1.second, p2.second);
}

int32_t main(){
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int h, w, k, l;
    cin>>h>>w>>k>>l;
    swap(h, w);
    int xh, yh, xv, yv;
    cin>>xh>>yh>>xv>>yv;

    pair<int, int> f;
    vector<vector<char> > a(h, vector<char>(w));
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin>>a[i][j];
            if(a[i][j] == '*'){
                f = {i, j};
            }
        }
    }

    vector<vector<int> > left(h, vector<int>(w, -1));
    vector<vector<int> > right(h, vector<int>(w, w));
    vector<vector<int> > up(h, vector<int>(w, -1));
    vector<vector<int> > down(h, vector<int>(w, h));

    int pre;
    for(int i = 0; i < h; i++){
        pre = -1;
        for(int j = 0; j < w; j++){
            if(a[i][j] == 'X') pre = j;
            left[i][j] = pre;
        }
    }

    for(int i = 0; i < h; i++){
        pre = w;
        for(int j = w-1; j >= 0; j--){
            if(a[i][j] == 'X') pre = j;
            right[i][j] = pre;
        }
    }

    for(int i = 0; i < w; i++){
        pre = -1;
        for(int j = 0; j < h; j++){
            if(a[j][i] == 'X') pre = j;
            up[j][i] = pre;
        }
    }

    for(int i = 0; i < w; i++){
        pre = h;
        for(int j = h-1; j >= 0; j--){
            if(a[j][i] == 'X') pre = j;
            down[j][i] = pre;
        }
    }

    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            left[i][j]++;
            up[i][j]++;
            down[i][j] -= l;
            right[i][j] -= k;
        }
    }

    vector<vector<bool> > vis(h, vector<bool>(w));
    pair<int, int> s = {yh, xv};
    queue<pair<int, int> > q;
    q.push(s);
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if(vis[x][y]) continue;
        vis[x][y] = 1;

        if(x > 0 && !vis[x-1][y]){
            bool pos = (left[x-1][y] <= right[x-1][y] && up[x-1][y] <= down[x-1][y]);
            pos &= (intersect({left[x-1][y], right[x-1][y]}, {left[x][y], right[x][y]}));
            pos &= (intersect({up[x-1][y], down[x-1][y]}, {up[x][y], down[x][y]}));
            if(pos) q.push({x-1, y});
        }

        if(x < h-1 && !vis[x+1][y]){
            bool pos = (left[x+1][y] <= right[x+1][y] && up[x+1][y] <= down[x+1][y]);
            pos &= (intersect({left[x+1][y], right[x+1][y]}, {left[x][y], right[x][y]}));
            pos &= (intersect({up[x+1][y], down[x+1][y]}, {up[x][y], down[x][y]}));
            if(pos) q.push({x+1, y});
        }

        if(y > 0 && !vis[x][y-1]){
            bool pos = (left[x][y-1] <= right[x][y-1] && up[x][y-1] <= down[x][y-1]);
            pos &= (intersect({left[x][y-1], right[x][y-1]}, {left[x][y], right[x][y]}));
            pos &= (intersect({up[x][y-1], down[x][y-1]}, {up[x][y], down[x][y]}));
            if(pos) q.push({x, y-1});
        }

        if(y < w-1 && !vis[x][y+1]){
            bool pos = (left[x][y+1] <= right[x][y+1] && up[x][y+1] <= down[x][y+1]);
            pos &= (intersect({left[x][y+1], right[x][y+1]}, {left[x][y], right[x][y]}));
            pos &= (intersect({up[x][y+1], down[x][y+1]}, {up[x][y], down[x][y]}));
            if(pos) q.push({x, y+1});
        }
    }

    if(vis[f.first][f.second]) cout<<"YES"<<endl;
    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