Submission #401358

#	Time	Username	Problem	Language	Result	Execution time	Memory
401358		cpp219	Furniture (JOI20_furniture)	C++14	100 / 100	435 ms	27816 KiB

furniture

#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e3 + 6;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
///Road to EF

ll n,m,a[N][N],was1[N][N],live[N][N],x,y,Q,was2[N][N];
ll dx[4] = {0,0,1,-1};
ll dy[4] = {1,-1,0,0};
bool chk(ll x,ll y){
    return x <= n&&y <= m&&x > 0&&y > 0&&!a[x][y];
}

ll f1(ll x,ll y){
    if (x == n&&y == m) return was1[x][y] = 1;
    if (was1[x][y] != -1) return was1[x][y];
    ll ans = 0;
    if (chk(x + 1,y)) ans = max(ans,f1(x + 1,y));
    if (chk(x,y + 1)) ans = max(ans,f1(x,y + 1));
    return was1[x][y] = ans;
}

ll f2(ll x,ll y){
    if (x == 1&&y == 1) return was2[x][y] = 1;
    if (was2[x][y] != -1) return was2[x][y];
    ll ans = 0;
    if (chk(x - 1,y)) ans = max(ans,f2(x - 1,y));
    if (chk(x,y - 1)) ans = max(ans,f2(x,y - 1));
    return was2[x][y] = ans;
}

bool Is_live(ll x,ll y){
    bool f1 = 0,f2 = 0;
    f1 = max(live[x][y + 1],live[x + 1][y]);
    f2 = max(live[x - 1][y],live[x][y - 1]);
    return min(f1,f2);
}
ll cnt[3*N];

ll BFS(ll x,ll y){
    if (!live[x][y]) return 1;
    if (cnt[x + y] == 1) return 0;
    queue<LL> q; q.push({x,y});
    while(!q.empty()){
        LL t = q.front(); q.pop();
        if (t.fs == 1&&t.sc == 1) continue;
        if (t.fs == n&&t.sc == m) continue;
        cnt[t.fs + t.sc]--; live[t.fs][t.sc] = 0; //cout<<Is_live(1,1); exit(0);
        for (ll i = 0;i < 4;i++){
            ll u = t.fs + dx[i],v = t.sc + dy[i]; //cout<<Is_live(1,1); exit(0);
            if (chk(u,v) && !Is_live(u,v) && live[u][v]) q.push({u,v});
        }
    }
    //cout<<cnt[3]<<"x"; exit(0);
    return 1;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "tst"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>m; memset(was1,-1,sizeof(was1)); memset(was2,-1,sizeof(was2));
    for (ll i = 1;i <= n;i++)
        for (ll j = 1;j <= m;j++) cin>>a[i][j];
    for (ll i = 1;i <= n;i++)
        for (ll j = 1;j <= m;j++){
            if (f1(i,j) && !a[i][j] && f2(i,j)) cnt[i + j]++,live[i][j] = 1;
        }
    //cout<<f1(2,2)<<" "<<f2(2,2); return 0;
    cin>>Q;
    while(Q--){
        cin>>x>>y;
        cout<<BFS(x,y)<<"\n";
    }
}

Compilation message (stderr)

furniture.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
furniture.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
furniture.cpp: In function 'int main()':
furniture.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   73 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95