oj.uz

Submission #849832

# Submission time Handle Problem Language Result Execution time Memory
849832 2023-09-15T12:25:01 Z Abito Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 40800 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define y1 YONE
typedef unsigned long long ull;
using namespace std;
const int N=3005;
int n,m,q,a[N][N],d[N][N],c,vis[N][N],f[N],e[N],dp[N][N];
bool b[N][N];
int rec(int x,int y,int dd){
    if (x>n || y>m || b[x][y]) {return INT_MIN;}
    if (x==n && y==m){
        d[x][y]=dd;
        return dp[x][y]=c;
    }if (vis[x][y]==-c) return dp[x][y];
    vis[x][y]=-c;
    dp[x][y]=max(rec(x+1,y,dd+1),rec(x,y+1,dd+1));
    d[x][y]=dd*bool(dp[x][y]==c);
    if (e[d[x][y]]==c) f[d[x][y]]++;
    else f[d[x][y]]=1,e[d[x][y]]=c;
    return dp[x][y];
}
void dfs1(int x,int y){
    f[d[x][y]]--;
    d[x][y]=0;
    if (x<n && !d[x+1][y-1] && d[x+1][y]) dfs1(x+1,y);
    if (y<m && !d[x-1][y+1] && d[x][y+1]) dfs1(x,y+1);
    return;
}
void dfs2(int x,int y){
    vis[x][y]=c;
    if (!d[x+1][y] && !d[x][y+1]) f[d[x][y]]--,d[x][y]=0;
    if (d[x][y]) return;
    if (x>1 && vis[x-1][y]!=c) dfs2(x-1,y);
    if (y>1 && vis[x][y-1]!=c) dfs2(x,y-1);
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>b[i][j];
    --c;rec(1,1,0);
    /*for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) cout<<dp[i][j]<<' ';
        cout<<endl;
    }*/
    cin>>q;
    while (q--){
        int x,y;cin>>x>>y;
        if (dp[x][y]!=c || !d[x][y]){
            b[x][y]=true;
            cout<<1<<endl;
            continue;
        }
        if (f[d[x][y]]>1 && e[d[x][y]]==c){
            b[x][y]=true;
            c++;
            rec(1,1,0);
            cout<<1<<endl;
            continue;
        }cout<<0<<endl;
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9176 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 30 ms 9052 KB Output is correct
4 Correct 45 ms 9332 KB Output is correct
5 Correct 63 ms 9352 KB Output is correct
6 Correct 134 ms 9376 KB Output is correct
7 Correct 20 ms 9308 KB Output is correct
8 Correct 19 ms 9380 KB Output is correct
9 Correct 30 ms 9396 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9176 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 30 ms 9052 KB Output is correct
4 Correct 45 ms 9332 KB Output is correct
5 Correct 63 ms 9352 KB Output is correct
6 Correct 134 ms 9376 KB Output is correct
7 Correct 20 ms 9308 KB Output is correct
8 Correct 19 ms 9380 KB Output is correct
9 Correct 30 ms 9396 KB Output is correct
10 Correct 51 ms 9552 KB Output is correct
11 Correct 34 ms 4956 KB Output is correct
12 Execution timed out 5082 ms 40800 KB Time limit exceeded
13 Halted 0 ms 0 KB -