oj.uz

Submission #401358

# Submission time Handle Problem Language Result Execution time Memory
401358 2021-05-10T02:19:24 Z cpp219 Furniture (JOI20_furniture) C++14
100 / 100
 435 ms 27816 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 6 ms 9012 KB Output is correct
3 Correct 6 ms 8908 KB Output is correct
4 Correct 7 ms 9036 KB Output is correct
5 Correct 8 ms 9036 KB Output is correct
6 Correct 8 ms 9040 KB Output is correct
7 Correct 9 ms 9036 KB Output is correct
8 Correct 8 ms 9164 KB Output is correct
9 Correct 8 ms 9036 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8780 KB Output is correct
2 Correct 6 ms 9012 KB Output is correct
3 Correct 6 ms 8908 KB Output is correct
4 Correct 7 ms 9036 KB Output is correct
5 Correct 8 ms 9036 KB Output is correct
6 Correct 8 ms 9040 KB Output is correct
7 Correct 9 ms 9036 KB Output is correct
8 Correct 8 ms 9164 KB Output is correct
9 Correct 8 ms 9036 KB Output is correct
10 Correct 19 ms 9032 KB Output is correct
11 Correct 7 ms 8652 KB Output is correct
12 Correct 242 ms 20724 KB Output is correct
13 Correct 103 ms 17712 KB Output is correct
14 Correct 370 ms 25228 KB Output is correct
15 Correct 405 ms 25632 KB Output is correct
16 Correct 387 ms 26440 KB Output is correct
17 Correct 418 ms 27332 KB Output is correct
18 Correct 411 ms 26808 KB Output is correct
19 Correct 435 ms 27816 KB Output is correct
20 Correct 406 ms 27756 KB Output is correct
21 Correct 420 ms 27784 KB Output is correct