oj.uz

Submission #1000538

# Submission time Handle Problem Language Result Execution time Memory
1000538 2024-06-17T16:46:06 Z HUYHDUVE Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 456 ms 124064 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define ff first
#define sc second
int const INF = 2e9;

vector<int> di = {1, -1, 0, 0}, dj = {0, 0, 1, -1};

int main(){
//    freopen("A.IN", "r", stdin);
//    freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<string> grid(n);
    for(auto &it : grid) cin >> it;

    vector<vector<int>> min_d(n, vector<int> (m, INF));
    min_d[0][0] = 1;
    deque<pii> q;
    q.push_back({0,0});
    int ans = 0;
    while(!q.empty()){
        pii cur = q.front();
        q.pop_front();
        ans = max(ans, min_d[cur.ff][cur.sc]);

        for(int i = 0; i < 4; i++){
            int ni = cur.ff + di[i];
            int nj = cur.sc + dj[i];
            if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            if(min_d[ni][nj] != INF || grid[ni][nj] == '.') continue;

            if(grid[cur.ff][cur.sc] == grid[ni][nj]){
                min_d[ni][nj] = min_d[cur.ff][cur.sc];
                q.push_front({ni, nj});
            }
            else {
                min_d[ni][nj] = min_d[cur.ff][cur.sc] + 1;
                q.push_back({ni, nj});
            }
        }
    }

    cout << ans;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1884 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 1372 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 2 ms 856 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 6 ms 1884 KB Output is correct
16 Correct 7 ms 1984 KB Output is correct
17 Correct 5 ms 1852 KB Output is correct
18 Correct 4 ms 1372 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 25 ms 9768 KB Output is correct
3 Correct 139 ms 96576 KB Output is correct
4 Correct 42 ms 22732 KB Output is correct
5 Correct 107 ms 54352 KB Output is correct
6 Correct 398 ms 110152 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 1 ms 880 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 864 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 24 ms 9820 KB Output is correct
14 Correct 14 ms 5768 KB Output is correct
15 Correct 9 ms 6232 KB Output is correct
16 Correct 12 ms 4188 KB Output is correct
17 Correct 73 ms 24704 KB Output is correct
18 Correct 43 ms 24324 KB Output is correct
19 Correct 43 ms 22872 KB Output is correct
20 Correct 32 ms 21040 KB Output is correct
21 Correct 82 ms 56148 KB Output is correct
22 Correct 102 ms 54268 KB Output is correct
23 Correct 148 ms 46740 KB Output is correct
24 Correct 84 ms 54704 KB Output is correct
25 Correct 212 ms 96592 KB Output is correct
26 Correct 207 ms 124064 KB Output is correct
27 Correct 277 ms 123240 KB Output is correct
28 Correct 388 ms 110308 KB Output is correct
29 Correct 456 ms 108380 KB Output is correct
30 Correct 340 ms 112648 KB Output is correct
31 Correct 322 ms 62212 KB Output is correct
32 Correct 235 ms 111928 KB Output is correct