Submission #1142955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142955		Mighilon	Toy (CEOI24_toy)	C++17	0 / 100	4 ms	2632 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define F0Rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;

void solve(){
    int w,h,k,l;
    cin>>w>>h>>k>>l;
    int hx,hy,vx,vy;//normal
    cin>>hx>>hy>>vx>>vy;
    vector<vi> a(h,vi(w));
    int fx,fy;
    F0R(i,h){
        F0R(j,w){
            char c;
            cin>>c;
            if(c=='X')
                a[i][j]=-1;
            else if(c=='*')
                fx=j,fy=i;
        }
    }
    vector<vi> vl(h,vi(w)),vr(h,vi(w,h-1));
    vector<vi> hl(h,vi(w)),hr(h,vi(w,w-1));
    F0R(i,h){
        F0R(j,w){
            if(!~a[i][j]) hl[i][j]=j;
            else if(j) hl[i][j]=hl[i][j-1];
            if(!~a[i][j]) vl[i][j]=i;
            else if(i) vl[i][j]=vl[i-1][j];
        }
    }
    F0Rd(i,h){
        F0Rd(j,w){
            if(!~a[i][j]) hr[i][j]=j;
            else if(j+1<w) hr[i][j]=hr[i][j+1];
            if(!~a[i][j]) vr[i][j]=i;
            else if(i+1<h) vr[i][j]=vr[i+1][j];
        }
    }

    vector<vi> p(h,vi(w));
    F0R(i,h){
        F0R(j,w){
            p[i][j]+=a[i][j]+1;
            if(i&&j)p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
            else if(i)p[i][j]+=p[i-1][j];
            else if(j)p[i][j]+=p[i][j-1];
        }
    }
    auto pp=[&](int y1,int x1,int y2,int x2)->int{
        if(y1&&x1)return p[y2][x2]-p[y2][x1-1]-p[y1-1][x2]+p[y1-1][x1-1];
        else if(y1)return p[y2][x2]-p[y1-1][x2];
        else if(x1)return p[y2][x2]-p[y2][x1-1];
        else return p[y2][x2];
    };
    auto verifh=[&](int y1,int x1,int y2,int x2){ //y1<=y2
        return pp(y1,max(hl[y1][x1],hl[y2][x2]),y2,min(hr[y1][x2],hr[y2][x2]))>=2*k;
    };
    auto verifv=[&](int y1,int x1,int y2,int x2){ //x1<=x2
        return pp(max(vl[y1][x1],vl[y2][x2]),x1,min(vr[y1][x1],vr[y2][x2]),x2)>=2*l;
    };
    queue<pi> q;
    q.push({hy,vx});
    a[hy][vx]=1;
    while(!q.empty()){
        auto [i,j]=q.front();
        q.pop();
        if(i&&!a[i-1][j]&&verifh(i-1,j,i,j)){
            a[i-1][j]=1;
            q.push({i-1,j});
        }
        if(i+1<h&&!a[i+1][j]&&verifh(i,j,i+1,j)){
            a[i+1][j]=1;
            q.push({i+1,j});
        }
        if(j&&!a[i][j-1]&&verifv(i,j-1,i,j)){
            a[i][j-1]=1;
            q.push({i,j-1});
        }
        if(j+1<w&&!a[i][j+1]&&verifv(i,j,i,j+1)){
            a[i][j+1]=1;
            q.push({i,j+1});
        }
    }
    if(a[fy][fx]==1)
        cout<<"YES\n";
    else cout<<"NO\n";
}
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

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