# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516552 | 2022-01-21T13:06:54 Z | DJ035 | Furniture (JOI20_furniture) | C++17 | 5000 ms | 10400 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]; queue<pi> q; ll bfs(){ memset(v, 0, sizeof(v)); q.push({0,0}); while(!q.empty()){ pi cur = q.front(); q.pop(); if(cur.x==n-1 && cur.y==m-1) return 1; //cout << "c " << cur.x << ' ' << cur.y << '\n'; if(!v[cur.x+1][cur.y] && !a[cur.x+1][cur.y] && (cur.x+1<n && cur.y<m)){ v[cur.x+1][cur.y] = 1; q.push({cur.x+1, cur.y}); } if(!v[cur.x][cur.y+1] && !a[cur.x][cur.y+1] && (cur.x<n && cur.y+1<m)){ v[cur.x][cur.y+1] = 1; q.push({cur.x, cur.y+1}); } } 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 | 386 ms | 10280 KB | Output is correct |
2 | Correct | 2613 ms | 10392 KB | Output is correct |
3 | Correct | 3099 ms | 10380 KB | Output is correct |
4 | Execution timed out | 5048 ms | 10400 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 386 ms | 10280 KB | Output is correct |
2 | Correct | 2613 ms | 10392 KB | Output is correct |
3 | Correct | 3099 ms | 10380 KB | Output is correct |
4 | Execution timed out | 5048 ms | 10400 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |