Submission #1069840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069840		vjudge1	Toy (CEOI24_toy)	C++17	100 / 100	373 ms	373012 KiB

Main

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pii pair<int,int>
pii bad = {-1,-1};
int w,h,k,l;

int presjek(pii a,pii b)
{
    if (a.ff > b.ff)
        swap(a,b);
    if (a.ss < b.ff)
        return 0;
    if (b.ss < a.ss)
        return (b.ss-b.ff+1);
    return a.ss-b.ff+1;
    
}
vector<pii> delta = {{0,1},{1,0},{-1,0},{0,-1}};
pii add(pii a,pii b)
{
    return {a.ff+b.ff,a.ss+b.ss};
}
pii sub(pii a,pii b)
{
    return {a.ff-b.ff,a.ss-b.ss};
}
void dfs(vector<vector<bool>>& vis,vector<vector<pii>>& rowsegment,vector<vector<pii>>& colsegment,pii cur, pii prev)
{
    //cout << "{" << prev.ff << "," << prev.ss << "}\n";
    //cout << "{" << cur.ff << "," << cur.ss << "}\n";
    //cout << endl;
    if (cur.ff < 0 || cur.ff > h-1 || 
    cur.ss < 0 || cur.ss > w-1 
    || vis[cur.ff][cur.ss] || (colsegment[cur.ff][cur.ss] == bad))
        return;
    pii raz = sub(cur,prev);
    
   
    if (abs(raz.ff) < abs(raz.ss))
    {
       
        if (presjek(colsegment[cur.ff][cur.ss],colsegment[prev.ff][prev.ss]) >= l)
        {
            vis[cur.ff][cur.ss] = 1;
            for (int del = 0; del < 4; del++)
            {
                pii cand = add(cur,delta[del]);
            
                 dfs(vis,rowsegment,colsegment,cand,cur);
            }
        }
    }
    else if(abs(raz.ff) > abs(raz.ss))
    {
        
        if (presjek(rowsegment[cur.ff][cur.ss],rowsegment[prev.ff][prev.ss]) >= k)
        {
            vis[cur.ff][cur.ss] = 1;
            for (int del = 0; del < 4; del++)
            {
                pii cand = add(cur,delta[del]);
                dfs(vis,rowsegment,colsegment,cand,cur);
            }
        }
    }
    else
    {
        vis[cur.ff][cur.ss] = 1;
            for (int del = 0; del < 4; del++)
            {
                pii cand = add(cur,delta[del]);
                dfs(vis,rowsegment,colsegment,cand,cur);
            }
    }
}
signed main() {
    
    cin >> w >> h >> k >> l;
    int xh,yh,xv,yv;
    cin >> xh >> yh >> xv >> yv;
    vector<vector<int>> grid(h,vector<int>(w,0));
    pii win;
    for (int i = 0; i < h; i++)
    {
        string s;
        cin >> s;
            
        for (int j = 0; j < w; j++)
        {
            if (s[j] == 'X')
                grid[i][j] = 1;
            if (s[j] == '*')
                win = {i,j};
        }
    }
    
    //The rows are numbered from 0 to H − 1 from top to bottom and columns are numbered 0 to
    //W − 1 from left to right. The x coordinate denotes the column number and y coordinate denotes
    //the row number
    vector<vector<pii>> rowsegment(h,vector<pii>(w,bad));
    vector<vector<pii>> colsegment(h,vector<pii>(w,bad));
    for (int i = 0; i < h; i++)
    {
        int prev = 0;
        for (int j = 0; j < w; j++)
        {
            if (!grid[i][j])
                rowsegment[i][j].ff = prev;
            else
                prev = j+1;
        }
        prev = w-1;
        for (int j = w-1; j >= 0; j--)
        {
            if (!grid[i][j])
                rowsegment[i][j].ss = prev;
            else
                prev = j-1;
        }
    }
    for (int j = 0; j < w; j++)
    {
        int prev = 0;
        for (int i = 0; i < h; i++)
        {
            if (!grid[i][j])
                colsegment[i][j].ff = prev;
            else
                prev = i+1;
        }
        prev = h-1;
        for (int i = h-1; i >= 0; i--)
        {
            if (!grid[i][j])
                colsegment[i][j].ss = prev;
            else
                prev = i-1;
        }
    }
    vector<vector<bool>> vis(h,vector<bool>(w,0));
    //vertical part ide po redovima a horizontal po kolonama
    pii start = {yh,xv};
    
    dfs(vis,rowsegment,colsegment,start,start);
  
    
    if (vis[win.ff][win.ss])
    {
        cout << "YES\n";
    }
    else
        cout << "NO\n";
}

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