oj.uz

Submission #746795

# Submission time Handle Problem Language Result Execution time Memory
746795 2023-05-23T06:11:47 Z Github Tracks in the Snow (BOI13_tracks) C++17
31.7708 / 100
 653 ms 222312 KB 
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

#define speedup ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const int MAXN = 4500;

char grid[MAXN][MAXN];
int dist[MAXN][MAXN];
int dX[] = {1, -1, 0, 0};
int dY[] = {0, 0, 1, -1};
int h, w;

int main(){
    speedup
    cin >> h >> w;
    for (int i = 0; i < h; i++){
        string s; cin >> s;
        for (int j = 0; j < w; j++){
            grid[i][j] = s[j];
        }
    }
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    for (int i = 0; i < MAXN; i++){
        for (int j = 0; j < MAXN; j++){
            dist[i][j] = 0;
        }
    }
    dist[0][0] = 1;
    int ans = 1;
    while (!q.empty()){
        auto&[x, y] = q.front(); q.pop_front();
        ans = max(ans, dist[x][y]);
        for (int i = 0; i < 4; i++){
            int nX = x+dX[i], nY = y+dY[i];
            if (nX >= 0 && nX < h && nY >= 0 && nY < w && grid[nX][nY] != '.' && dist[nX][nY] == 0){
                if (grid[nX][nY] == grid[x][y]){
                    dist[nX][nY] = dist[x][y];
                    q.push_front({nX, nY});
                }else{
                    dist[nX][nY] = dist[x][y]+1;
                    q.push_back({nX, nY});
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 81704 KB Output isn't correct
2 Correct 30 ms 79632 KB Output is correct
3 Incorrect 30 ms 79752 KB Output isn't correct
4 Incorrect 34 ms 81804 KB Output isn't correct
5 Incorrect 31 ms 80784 KB Output isn't correct
6 Correct 31 ms 79512 KB Output is correct
7 Incorrect 30 ms 79768 KB Output isn't correct
8 Incorrect 31 ms 79760 KB Output isn't correct
9 Incorrect 33 ms 79900 KB Output isn't correct
10 Incorrect 33 ms 80528 KB Output isn't correct
11 Incorrect 32 ms 80380 KB Output isn't correct
12 Incorrect 33 ms 80796 KB Output isn't correct
13 Incorrect 34 ms 80700 KB Output isn't correct
14 Incorrect 39 ms 80760 KB Output isn't correct
15 Incorrect 39 ms 81740 KB Output isn't correct
16 Incorrect 41 ms 81660 KB Output isn't correct
17 Incorrect 37 ms 81644 KB Output isn't correct
18 Incorrect 34 ms 81764 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 94836 KB Output is correct
2 Incorrect 59 ms 85112 KB Output isn't correct
3 Incorrect 65 ms 97200 KB Output isn't correct
4 Incorrect 67 ms 87884 KB Output isn't correct
5 Correct 142 ms 92732 KB Output is correct
6 Runtime error 653 ms 213492 KB Execution killed with signal 11
7 Correct 34 ms 95564 KB Output is correct
8 Correct 35 ms 94816 KB Output is correct
9 Incorrect 31 ms 79584 KB Output isn't correct
10 Correct 30 ms 79612 KB Output is correct
11 Correct 42 ms 95256 KB Output is correct
12 Correct 32 ms 80140 KB Output is correct
13 Incorrect 54 ms 85104 KB Output isn't correct
14 Incorrect 47 ms 83520 KB Output isn't correct
15 Correct 43 ms 83920 KB Output is correct
16 Incorrect 43 ms 81352 KB Output isn't correct
17 Incorrect 70 ms 88400 KB Output isn't correct
18 Correct 79 ms 88404 KB Output is correct
19 Incorrect 68 ms 87840 KB Output isn't correct
20 Incorrect 40 ms 87300 KB Output isn't correct
21 Incorrect 64 ms 93236 KB Output isn't correct
22 Correct 141 ms 92716 KB Output is correct
23 Incorrect 57 ms 90548 KB Output isn't correct
24 Correct 121 ms 93328 KB Output is correct
25 Correct 347 ms 97224 KB Output is correct
26 Correct 407 ms 145192 KB Output is correct
27 Incorrect 617 ms 130528 KB Output isn't correct
28 Runtime error 609 ms 213488 KB Execution killed with signal 11
29 Runtime error 609 ms 210060 KB Execution killed with signal 11
30 Runtime error 602 ms 222312 KB Execution killed with signal 11
31 Incorrect 420 ms 94000 KB Output isn't correct
32 Runtime error 504 ms 219940 KB Execution killed with signal 11