oj.uz

Submission #882791

# Submission time Handle Problem Language Result Execution time Memory
882791 2023-12-03T17:55:37 Z vincentbucourt1 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 595 ms 130704 KB 
#include <bits/stdc++.h>

using namespace std;

string pic[4000];
int minLen[4000][4000];
int H, W;

int Y[4] = {0, 0, 1, -1}, X[4] = {1, -1, 0, 0};

bool inRec(int Y, int X){
    return (Y > -1 && Y < H && X > -1 && X < W && pic[Y][X] != '.');
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> H >> W;
    
    for (int i = 0; i < H; i++){
        cin >> pic[i];
    }
    
    deque<pair<int, int>> Q; // {X, Y}
    pair<int, int> on;
    int M = 0;
    Q.push_front({0, 0});
    minLen[0][0] = 1;
    
    while (!Q.empty()){
        on = Q.front();
        Q.pop_front();
        M = max(M, minLen[on.second][on.first]);
        
        for (int i = 0; i < 4; i++){
            
            int onX = on.first + X[i], onY = on.second + Y[i];
            
            if (inRec(onY, onX) && minLen[onY][onX] == 0){
                if (pic[on.second][on.first] == pic[onY][onX]){
                    Q.push_front({onX, onY});
                    minLen[onY][onX] = minLen[on.second][on.first];
                }
                else{
                    Q.push_back({onX, onY});
                    minLen[onY][onX] = minLen[on.second][on.first] + 1;
                }
            }
        }
    }
    
    cout << M;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3800 KB Output is correct
2 Correct 1 ms 668 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 2 ms 1688 KB Output is correct
11 Correct 2 ms 1676 KB Output is correct
12 Correct 4 ms 2224 KB Output is correct
13 Correct 2 ms 1964 KB Output is correct
14 Correct 3 ms 1944 KB Output is correct
15 Correct 8 ms 3620 KB Output is correct
16 Correct 10 ms 3908 KB Output is correct
17 Correct 6 ms 3676 KB Output is correct
18 Correct 5 ms 3416 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15964 KB Output is correct
2 Correct 30 ms 11904 KB Output is correct
3 Correct 157 ms 75456 KB Output is correct
4 Correct 50 ms 29404 KB Output is correct
5 Correct 89 ms 51584 KB Output is correct
6 Correct 568 ms 109644 KB Output is correct
7 Correct 8 ms 16732 KB Output is correct
8 Correct 7 ms 15964 KB Output is correct
9 Correct 2 ms 956 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 7 ms 16420 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 30 ms 11864 KB Output is correct
14 Correct 18 ms 8028 KB Output is correct
15 Correct 13 ms 10344 KB Output is correct
16 Correct 14 ms 5080 KB Output is correct
17 Correct 74 ms 25328 KB Output is correct
18 Correct 59 ms 32244 KB Output is correct
19 Correct 49 ms 29268 KB Output is correct
20 Correct 43 ms 22460 KB Output is correct
21 Correct 95 ms 50456 KB Output is correct
22 Correct 88 ms 51540 KB Output is correct
23 Correct 151 ms 42344 KB Output is correct
24 Correct 96 ms 47532 KB Output is correct
25 Correct 386 ms 96264 KB Output is correct
26 Correct 595 ms 130704 KB Output is correct
27 Correct 533 ms 114492 KB Output is correct
28 Correct 531 ms 109688 KB Output is correct
29 Correct 509 ms 107384 KB Output is correct
30 Correct 542 ms 111780 KB Output is correct
31 Correct 384 ms 72164 KB Output is correct
32 Correct 493 ms 112616 KB Output is correct