oj.uz

Submission #421256

# Submission time Handle Problem Language Result Execution time Memory
421256 2021-06-08T23:28:37 Z pavanscoding Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 789 ms 130744 KB 
#include <bits/stdc++.h>
using namespace std;

int dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0};
int n,m,depth[4000][4000], ans=1;
string grid[4000];

bool check(int x, int y){
    return (x>-1&&x<n&&y>-1&&y<m&&grid[x][y]!='.');
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=0;i<n;i++)
        cin >> grid[i];
    deque<pair<int,int>> q;
    q.push_back({0,0});
    depth[0][0]=1;

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

        for(int i=0;i<4;i++){
            int x=t.first+dx[i], y=t.second+dy[i];
            if(check(x,y)&&depth[x][y]==0){
                if(grid[x][y]==grid[t.first][t.second]){    
                    depth[x][y]=depth[t.first][t.second];
                    q.push_front({x,y});
                }
                else{
                    depth[x][y]=depth[t.first][t.second]+1;
                    q.push_back({x,y});
                }
            }
        }
    }
    cout << ans << "\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3788 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 8 ms 3396 KB Output is correct
5 Correct 3 ms 1988 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 832 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 10 ms 3656 KB Output is correct
16 Correct 13 ms 3868 KB Output is correct
17 Correct 9 ms 3676 KB Output is correct
18 Correct 8 ms 3428 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15820 KB Output is correct
2 Correct 38 ms 11784 KB Output is correct
3 Correct 189 ms 75268 KB Output is correct
4 Correct 61 ms 29340 KB Output is correct
5 Correct 144 ms 51652 KB Output is correct
6 Correct 647 ms 109452 KB Output is correct
7 Correct 11 ms 16588 KB Output is correct
8 Correct 10 ms 15888 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 11 ms 16232 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 38 ms 11844 KB Output is correct
14 Correct 22 ms 7860 KB Output is correct
15 Correct 18 ms 10316 KB Output is correct
16 Correct 21 ms 4908 KB Output is correct
17 Correct 99 ms 25260 KB Output is correct
18 Correct 75 ms 32120 KB Output is correct
19 Correct 62 ms 29596 KB Output is correct
20 Correct 48 ms 22420 KB Output is correct
21 Correct 118 ms 50484 KB Output is correct
22 Correct 151 ms 51652 KB Output is correct
23 Correct 191 ms 42308 KB Output is correct
24 Correct 125 ms 47592 KB Output is correct
25 Correct 430 ms 96272 KB Output is correct
26 Correct 789 ms 130744 KB Output is correct
27 Correct 597 ms 114504 KB Output is correct
28 Correct 635 ms 109520 KB Output is correct
29 Correct 625 ms 107196 KB Output is correct
30 Correct 658 ms 111760 KB Output is correct
31 Correct 497 ms 72072 KB Output is correct
32 Correct 693 ms 112392 KB Output is correct