oj.uz

Submission #464488

# Submission time Handle Problem Language Result Execution time Memory
464488 2021-08-13T09:58:29 Z Aratab Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 633 ms 130928 KB 
/**
 * Author : Samuel Batara (Aratab)
**/ 
#include <bits/stdc++.h>
using namespace std;

int N,M;
string s[4001];
int dep[4001][4001];
vector<int> dx = {1,0,-1,0};
vector<int> dy = {0,1,0,-1};

bool inside(int x, int y) {
    return (x>-1 && x<N && y>-1 && y<M && s[x][y]!='.');
}

void dahiken() {
    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> s[i];
    dep[0][0] = 1;
    deque<pair<int,int>> q;
    q.push_back({0,0});
    int ans = 1;
    while(!q.empty()) {
        int a,b; tie(a,b) = q.front(); q.pop_front();
        ans = max(ans, dep[a][b]);
        for(int i=0; i<4; i++) {
            int x = a + dx[i], y = b + dy[i];
            if(inside(x,y) && dep[x][y]==0) {
                if(s[a][b] == s[x][y]) {
                    dep[x][y] = dep[a][b];
                    q.push_front({x,y});
                } else {
                    dep[x][y] = dep[a][b] + 1;
                    q.push_back({x,y});
                }
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int ntc=1;
    //cin >> ntc;
    while(ntc--) {
        dahiken();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3788 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 8 ms 3532 KB Output is correct
5 Correct 3 ms 1996 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 3 ms 1612 KB Output is correct
11 Correct 3 ms 1484 KB Output is correct
12 Correct 5 ms 2124 KB Output is correct
13 Correct 3 ms 1996 KB Output is correct
14 Correct 3 ms 1996 KB Output is correct
15 Correct 11 ms 3664 KB Output is correct
16 Correct 12 ms 3820 KB Output is correct
17 Correct 9 ms 3644 KB Output is correct
18 Correct 8 ms 3532 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15948 KB Output is correct
2 Correct 39 ms 11924 KB Output is correct
3 Correct 205 ms 75492 KB Output is correct
4 Correct 67 ms 29320 KB Output is correct
5 Correct 166 ms 51344 KB Output is correct
6 Correct 617 ms 110308 KB Output is correct
7 Correct 11 ms 16588 KB Output is correct
8 Correct 10 ms 15948 KB Output is correct
9 Correct 2 ms 820 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 11 ms 16332 KB Output is correct
12 Correct 1 ms 1096 KB Output is correct
13 Correct 39 ms 11904 KB Output is correct
14 Correct 23 ms 7856 KB Output is correct
15 Correct 20 ms 10348 KB Output is correct
16 Correct 19 ms 4932 KB Output is correct
17 Correct 100 ms 25148 KB Output is correct
18 Correct 111 ms 32084 KB Output is correct
19 Correct 63 ms 29288 KB Output is correct
20 Correct 50 ms 22360 KB Output is correct
21 Correct 124 ms 50600 KB Output is correct
22 Correct 165 ms 51396 KB Output is correct
23 Correct 198 ms 42436 KB Output is correct
24 Correct 147 ms 47492 KB Output is correct
25 Correct 421 ms 96256 KB Output is correct
26 Correct 398 ms 130680 KB Output is correct
27 Correct 519 ms 130928 KB Output is correct
28 Correct 633 ms 110364 KB Output is correct
29 Correct 624 ms 107888 KB Output is correct
30 Correct 573 ms 113624 KB Output is correct
31 Correct 490 ms 71988 KB Output is correct
32 Correct 446 ms 118392 KB Output is correct