oj.uz

Submission #791576

# Submission time Handle Problem Language Result Execution time Memory
791576 2023-07-24T07:37:56 Z Cookie Portals (BOI14_portals) C++14
20 / 100
 5 ms 1620 KB 
#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define int long long
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mxn = 2e6 + 5, base = 972663749;
const ll mod = 911382323, inf = 1e9;
int r, c;
pii st, en;
char a[1005][1005];
int dis[1005][1005];
bool safe(int i, int j){
    return(i >= 1 && j >= 1 && i <= r && j <= c && a[i][j] != '#');
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> r >> c;
    forr(i, 1, r + 1){
        forr(j, 1, c + 1){
            cin >> a[i][j];
            if(a[i][j] == 'S'){
                st = make_pair(i, j);
            }else if(a[i][j] == 'C'){
                en = make_pair(i, j);
            }
            dis[i][j] = -1;
        }
    }
    queue<pii>q; q.push(st); dis[st.fi][st.se] = 0;
    while(!q.empty()){
        auto [cox, coy] = q.front(); q.pop();
        forr(i, 0, 4){
            int nwx = cox + x[i], nwy = coy + y[i];
            if(safe(nwx, nwy) && dis[nwx][nwy] == -1){
                dis[nwx][nwy] = dis[cox][coy] + 1;
                q.push({nwx, nwy});
            }else if(!safe(nwx, nwy)){
                forr(j, 0, 4){
                    if(i == j)continue;
                    int yesx = cox, yesy = coy;
                    while(safe(yesx + x[j], yesy + y[j])){
                        yesx += x[j]; yesy += y[j];
                    }
                    if(dis[yesx][yesy] == -1){
                        dis[yesx][yesy] = dis[cox][coy] + 1;
                        q.push({yesx, yesy});
                    }
                }
                
            }
        }
    }
    cout << dis[en.fi][en.se];
    return(0);
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:49:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         auto [cox, coy] = q.front(); q.pop();
      |              ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 592 KB Output is correct
10 Incorrect 1 ms 596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 5 ms 1620 KB Output is correct
6 Correct 4 ms 1620 KB Output is correct
7 Correct 5 ms 1620 KB Output is correct
8 Correct 2 ms 1620 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Incorrect 1 ms 596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Incorrect 1 ms 584 KB Output isn't correct
11 Halted 0 ms 0 KB -