# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516546 | 2022-01-21T13:01:22 Z | DJ035 | Furniture (JOI20_furniture) | C++17 | 5000 ms | 10440 KB |
# pragma GCC optimize ("O3") # pragma GCC optimize ("Ofast") # pragma GCC optimize ("unroll-loops") #include <bits/stdc++.h> #define MEM 1111 #define sanic ios_base::sync_with_stdio(0) #define x first #define y second #define pf push_front #define pb push_back #define all(v) v.begin(), v.end() #define sz size() using namespace std; typedef long long ll; typedef pair<ll, ll> pi; const ll MOD = 1e9+7; const ll INF = 2e14+7; ll mul(ll a, ll b){ return ((a*b)%MOD+MOD)%MOD; } ll add(ll a, ll b){ return ((a+b)%MOD+MOD)%MOD; } ll t,n,m,k; ll a[MEM][MEM], v[MEM][MEM]; string s; ll dx[2] = {1,0}; ll dy[2] = {0,1}; queue<pi> q; ll bfs(){ memset(v, 0, sizeof(v)); pi fin={n-1, m-1}; q.push({0,0}); while(!q.empty()){ pi cur = q.front(); q.pop(); if(cur==fin) return 1; //cout << "c " << cur.x << ' ' << cur.y << '\n'; for(int i=0; i<2; i++){ ll nx = cur.x+dx[i], ny = cur.y+dy[i]; //cout <<'\n' << nx << ' ' << ny << ' '; if((nx>=n || ny>=m) || a[nx][ny] || v[nx][ny]) continue; //cout << "p "; v[nx][ny] = 1; //cout << "p "; q.push({nx,ny}); } } return 0; } signed main(){ //sanic; cin.tie(0); cout.tie(0); scanf("%lld %lld ", &n, &m); for(int i=0; i<n; i++) for(int j=0; j<m; j++) scanf("%lld ", &a[i][j]); scanf("%lld ", &t); while(t--){ ll q1,q2; scanf("%lld %lld ", &q1, &q2); if(a[q1-1][q2-1]){ puts("0"); continue; } a[q1-1][q2-1] = 1; ll f=bfs(); if(f) puts("1"); else { puts("0"); a[q1-1][q2-1] = 0; } } } /* 6 2 3 4 3 1 3 3 5 6 2 110011 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 356 ms | 10280 KB | Output is correct |
2 | Correct | 2564 ms | 10388 KB | Output is correct |
3 | Correct | 3021 ms | 10440 KB | Output is correct |
4 | Execution timed out | 5091 ms | 10404 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 356 ms | 10280 KB | Output is correct |
2 | Correct | 2564 ms | 10388 KB | Output is correct |
3 | Correct | 3021 ms | 10440 KB | Output is correct |
4 | Execution timed out | 5091 ms | 10404 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |