oj.uz

Submission #613938

# Submission time Handle Problem Language Result Execution time Memory
613938 2022-07-30T13:53:05 Z HediChehaidar Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 7288 KB 
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = 1e9 + 7;//998244353 ;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

int n , m , q;
int g[1010][1010];
bool vis[1010][1010];

void dfs(int x , int y){
    if( x == n + 1 || y == m + 1 || vis[x][y] || g[x][y]) return ;
    vis[x][y] = true;
    dfs(x + 1 , y); dfs(x , y + 1);
}
int main(){
    //ifstream fin ("testing.txt");
    //ofstream fout ("output.txt");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <=m ; j++) cin>>g[i][j];
    }
    cin>>q;
    while(q--){
        int x , y ; cin>>x>>y;
        g[x][y] = 1;
        for(int i = 1 ; i <= n ; i++) for(int j = 1 ; j <= m ; j++) vis[i][j] = false;
        dfs(1 , 1);
        cout << vis[n][m] << "\n";
        if(!vis[n][m]) g[x][y] = 0;
    }
    return 0;
}

/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO / HLD
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 712 KB Output is correct
2 Correct 13 ms 864 KB Output is correct
3 Correct 54 ms 812 KB Output is correct
4 Correct 88 ms 856 KB Output is correct
5 Correct 90 ms 880 KB Output is correct
6 Correct 149 ms 900 KB Output is correct
7 Correct 62 ms 904 KB Output is correct
8 Correct 94 ms 856 KB Output is correct
9 Correct 184 ms 900 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 712 KB Output is correct
2 Correct 13 ms 864 KB Output is correct
3 Correct 54 ms 812 KB Output is correct
4 Correct 88 ms 856 KB Output is correct
5 Correct 90 ms 880 KB Output is correct
6 Correct 149 ms 900 KB Output is correct
7 Correct 62 ms 904 KB Output is correct
8 Correct 94 ms 856 KB Output is correct
9 Correct 184 ms 900 KB Output is correct
10 Correct 2535 ms 1032 KB Output is correct
11 Correct 101 ms 620 KB Output is correct
12 Execution timed out 5082 ms 7288 KB Time limit exceeded
13 Halted 0 ms 0 KB -