oj.uz

Submission #786053

# Submission time Handle Problem Language Result Execution time Memory
786053 2023-07-18T00:45:31 Z orcslop Tracks in the Snow (BOI13_tracks) C++17
32.1875 / 100
 25 ms 3124 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 505; 
const int dx[4] = {-1, 1, 0, 0}; 
const int dy[4] = {0, 0, -1, 1}; 

int n, m; 
char snow[MAXN][MAXN]; 
int depth[MAXN][MAXN]; 
deque<pair<int, int>> dq; 

bool inbounds(int x, int y){
    return (x >= 0 && y >= 0 && x < n && y < m && snow[x][y] != '.'); 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m; 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> snow[i][j]; 
        }
    }
    depth[0][0] = 1; 
    dq.push_back(make_pair(0, 0)); 
    int ans = 0; 

    while(!dq.empty()){
        pair<int, int> curr = dq.front(); 
        dq.pop_front(); 
        ans = max(ans, depth[curr.first][curr.second]); 

        for(int i = 0; i < 4; i++){
            int x = curr.first + dx[i]; 
            int y = curr.second + dy[i]; 
            if(inbounds(x, y) && !depth[x][y]){
                if(snow[x][y] == snow[curr.first][curr.second]){
                    depth[x][y] = depth[curr.first][curr.second]; 
                    dq.push_front(make_pair(x, y)); 
                }
                else{
                    depth[x][y] = depth[curr.first][curr.second] + 1; 
                    dq.push_back(make_pair(x, y)); 
                }
            }
        }
    }

    cout << ans << '\n'; 
    return 0; 
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1748 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 7 ms 1868 KB Output is correct
5 Correct 3 ms 1112 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 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 980 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 4 ms 1112 KB Output is correct
13 Correct 2 ms 1112 KB Output is correct
14 Correct 2 ms 1108 KB Output is correct
15 Correct 8 ms 1840 KB Output is correct
16 Correct 9 ms 1748 KB Output is correct
17 Correct 7 ms 1748 KB Output is correct
18 Correct 5 ms 1876 KB Output is correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 11
2 Runtime error 8 ms 1772 KB Execution killed with signal 11
3 Runtime error 20 ms 3096 KB Execution killed with signal 11
4 Runtime error 10 ms 2008 KB Execution killed with signal 11
5 Runtime error 17 ms 2564 KB Execution killed with signal 11
6 Runtime error 21 ms 3044 KB Execution killed with signal 11
7 Runtime error 1 ms 984 KB Execution killed with signal 11
8 Runtime error 1 ms 980 KB Execution killed with signal 11
9 Incorrect 1 ms 404 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Runtime error 1 ms 980 KB Execution killed with signal 11
12 Correct 1 ms 724 KB Output is correct
13 Runtime error 7 ms 1748 KB Execution killed with signal 11
14 Runtime error 6 ms 1712 KB Execution killed with signal 11
15 Runtime error 6 ms 1748 KB Execution killed with signal 11
16 Incorrect 8 ms 1332 KB Output isn't correct
17 Runtime error 10 ms 2012 KB Execution killed with signal 11
18 Runtime error 11 ms 2136 KB Execution killed with signal 11
19 Runtime error 10 ms 2004 KB Execution killed with signal 11
20 Runtime error 10 ms 2004 KB Execution killed with signal 11
21 Runtime error 15 ms 2580 KB Execution killed with signal 11
22 Runtime error 14 ms 2532 KB Execution killed with signal 11
23 Runtime error 14 ms 2644 KB Execution killed with signal 11
24 Runtime error 15 ms 2588 KB Execution killed with signal 11
25 Runtime error 21 ms 3100 KB Execution killed with signal 11
26 Runtime error 19 ms 2768 KB Execution killed with signal 11
27 Runtime error 18 ms 3092 KB Execution killed with signal 11
28 Runtime error 18 ms 3076 KB Execution killed with signal 11
29 Runtime error 19 ms 3124 KB Execution killed with signal 11
30 Runtime error 20 ms 3020 KB Execution killed with signal 11
31 Runtime error 15 ms 2640 KB Execution killed with signal 11
32 Runtime error 25 ms 3012 KB Execution killed with signal 11