# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
516556 | 2022-01-21T13:09:49 Z | DJ035 | Furniture (JOI20_furniture) | C++17 | 5000 ms | 2116 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]; bool v[MEM][MEM]; queue<pi> q; bool 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]){ printf("0\n"); continue; } a[q1-1][q2-1] = 1; ll f=bfs(); if(f) printf("1\n"); else { printf("0\n"); 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 | 39 ms | 1740 KB | Output is correct |
2 | Correct | 114 ms | 1868 KB | Output is correct |
3 | Correct | 210 ms | 1920 KB | Output is correct |
4 | Correct | 359 ms | 1948 KB | Output is correct |
5 | Correct | 400 ms | 1988 KB | Output is correct |
6 | Correct | 588 ms | 1976 KB | Output is correct |
7 | Correct | 433 ms | 1980 KB | Output is correct |
8 | Correct | 442 ms | 1968 KB | Output is correct |
9 | Correct | 676 ms | 1972 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 1740 KB | Output is correct |
2 | Correct | 114 ms | 1868 KB | Output is correct |
3 | Correct | 210 ms | 1920 KB | Output is correct |
4 | Correct | 359 ms | 1948 KB | Output is correct |
5 | Correct | 400 ms | 1988 KB | Output is correct |
6 | Correct | 588 ms | 1976 KB | Output is correct |
7 | Correct | 433 ms | 1980 KB | Output is correct |
8 | Correct | 442 ms | 1968 KB | Output is correct |
9 | Correct | 676 ms | 1972 KB | Output is correct |
10 | Execution timed out | 5040 ms | 2116 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |