oj.uz

Submission #476977

# Submission time Handle Problem Language Result Execution time Memory
476977 2021-09-29T16:06:04 Z asdf1234coding Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 704 ms 124108 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define MOD (ll) (1e9+7)

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int n,m; string board[4000]; 

bool inBounds(int x, int y) {
    return (x>=0 && x<n && y>=0 && y<m && board[x][y]!='.');
}

int main() {
    ios_base::sync_with_stdio(false);
    cin>>n>>m; //height n width m
    for(int i=0; i<n;i++) cin>>board[i];
    vector<vector<int>> dist(n, vector<int>(m, 0));
    int ans = 1;
    deque<pair<int,int>> q;
    dist[0][0] = 1;
    q.push_back({0,0});

    while(!q.empty()) {
        pair<int,int> curr = q.front();
        q.pop_front();
        ans = max(ans, dist[curr.first][curr.second]);
        for(int i=0; i<4; i++) {
            int x = curr.first + dx[i];
            int y = curr.second + dy[i];
            if(inBounds(x,y) && dist[x][y] == 0) {
                if(board[curr.first][curr.second] == board[x][y]) {
                    dist[x][y] = dist[curr.first][curr.second];
                    q.push_front({x,y});
                } else {
                    dist[x][y] = dist[curr.first][curr.second]+1;
                    q.push_back({x,y});
                }
            }
        }

    }
    cout<<ans<<endl; return 0;
    
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1868 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6 ms 1484 KB Output is correct
5 Correct 2 ms 844 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 4 ms 972 KB Output is correct
13 Correct 4 ms 844 KB Output is correct
14 Correct 2 ms 828 KB Output is correct
15 Correct 10 ms 1868 KB Output is correct
16 Correct 11 ms 1868 KB Output is correct
17 Correct 9 ms 1996 KB Output is correct
18 Correct 6 ms 1492 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 39 ms 9760 KB Output is correct
3 Correct 199 ms 96516 KB Output is correct
4 Correct 56 ms 22796 KB Output is correct
5 Correct 139 ms 54212 KB Output is correct
6 Correct 704 ms 109448 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 2 ms 832 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 37 ms 9676 KB Output is correct
14 Correct 22 ms 5836 KB Output is correct
15 Correct 15 ms 6348 KB Output is correct
16 Correct 19 ms 4280 KB Output is correct
17 Correct 101 ms 24624 KB Output is correct
18 Correct 61 ms 24280 KB Output is correct
19 Correct 61 ms 22732 KB Output is correct
20 Correct 46 ms 20872 KB Output is correct
21 Correct 119 ms 56116 KB Output is correct
22 Correct 148 ms 54248 KB Output is correct
23 Correct 190 ms 46792 KB Output is correct
24 Correct 125 ms 54720 KB Output is correct
25 Correct 408 ms 96516 KB Output is correct
26 Correct 588 ms 124108 KB Output is correct
27 Correct 641 ms 116320 KB Output is correct
28 Correct 688 ms 109524 KB Output is correct
29 Correct 643 ms 108212 KB Output is correct
30 Correct 664 ms 107768 KB Output is correct
31 Correct 537 ms 62236 KB Output is correct
32 Correct 646 ms 109372 KB Output is correct