oj.uz

Submission #746786

# Submission time Handle Problem Language Result Execution time Memory
746786 2023-05-23T06:00:56 Z Github Tracks in the Snow (BOI13_tracks) C++17
31.7708 / 100
 754 ms 260596 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;

bool possibility(int x, int y){
    if (x >= 0 && x < h && y >= 0 && y < w && grid[x][y] != '.'){
        return true;
    }
    return false;
}

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_front({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 (possibility(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 40 ms 81764 KB Output isn't correct
2 Correct 29 ms 79568 KB Output is correct
3 Incorrect 30 ms 79716 KB Output isn't correct
4 Incorrect 36 ms 81708 KB Output isn't correct
5 Incorrect 32 ms 80724 KB Output isn't correct
6 Correct 31 ms 79636 KB Output is correct
7 Incorrect 33 ms 79704 KB Output isn't correct
8 Incorrect 31 ms 79820 KB Output isn't correct
9 Incorrect 29 ms 79900 KB Output isn't correct
10 Incorrect 32 ms 80532 KB Output isn't correct
11 Incorrect 33 ms 80380 KB Output isn't correct
12 Incorrect 32 ms 80784 KB Output isn't correct
13 Incorrect 35 ms 80712 KB Output isn't correct
14 Incorrect 35 ms 80708 KB Output isn't correct
15 Incorrect 40 ms 81784 KB Output isn't correct
16 Incorrect 40 ms 81684 KB Output isn't correct
17 Incorrect 37 ms 81676 KB Output isn't correct
18 Incorrect 45 ms 81740 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94872 KB Output is correct
2 Incorrect 65 ms 85096 KB Output isn't correct
3 Incorrect 63 ms 97204 KB Output isn't correct
4 Incorrect 72 ms 87844 KB Output isn't correct
5 Correct 149 ms 92748 KB Output is correct
6 Incorrect 638 ms 105424 KB Output isn't correct
7 Correct 38 ms 95620 KB Output is correct
8 Correct 39 ms 94800 KB Output is correct
9 Incorrect 35 ms 79648 KB Output isn't correct
10 Correct 32 ms 79608 KB Output is correct
11 Correct 36 ms 95280 KB Output is correct
12 Correct 31 ms 80120 KB Output is correct
13 Incorrect 62 ms 85120 KB Output isn't correct
14 Incorrect 45 ms 83592 KB Output isn't correct
15 Correct 46 ms 83896 KB Output is correct
16 Incorrect 46 ms 81288 KB Output isn't correct
17 Incorrect 76 ms 88468 KB Output isn't correct
18 Correct 79 ms 88404 KB Output is correct
19 Incorrect 69 ms 88000 KB Output isn't correct
20 Incorrect 39 ms 87324 KB Output isn't correct
21 Incorrect 52 ms 93220 KB Output isn't correct
22 Correct 108 ms 92740 KB Output is correct
23 Incorrect 57 ms 90532 KB Output isn't correct
24 Correct 120 ms 93328 KB Output is correct
25 Correct 325 ms 97228 KB Output is correct
26 Correct 558 ms 145228 KB Output is correct
27 Runtime error 708 ms 260596 KB Execution killed with signal 11
28 Incorrect 681 ms 105428 KB Output isn't correct
29 Runtime error 707 ms 210396 KB Execution killed with signal 11
30 Runtime error 754 ms 223628 KB Execution killed with signal 11
31 Incorrect 392 ms 93948 KB Output isn't correct
32 Runtime error 673 ms 221932 KB Execution killed with signal 11