oj.uz

Submission #475812

# Submission time Handle Problem Language Result Execution time Memory
475812 2021-09-24T06:01:07 Z clams Tracks in the Snow (BOI13_tracks) C++17
19.7917 / 100
 910 ms 123128 KB 
/*
 * Author: bubu2006
**/

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int H, W;
    cin >> H >> W;
    
    vector<string> m(H);
    for(int i = 0; i < H; i++) cin >> m[i];
    
    vector<int> dy = {0, 0, -1, 1};
    vector<int> dx = {1, -1, 0, 0};
    
    const int INF = 1e8;
    
    vector<vector<int>> d(H, vector<int>(W, INF));
    deque<pair<int, int>> q;
    q.push_back({0, 0});
    d[0][0] = 1;
    
    int ans = 0;
    while(!q.empty()) {
        pair<int, int> cur = q.front();
        int y = cur.first;
        int x = cur.second;
        ans = max(ans, d[y][x]);
        q.pop_front();
        
        
        for(int k = 0; k < 4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];
            
            if(ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
            int w = (m[y][x] != m[ny][nx]);
            if(d[ny][nx] > d[y][x] + w) {
                d[ny][nx] = d[y][x] + w;
                if(w) q.push_back({ny, nx});
                else q.push_front({ny, nx});
            }
        }
    } 
    
    cout << ans << '\n';
}

// ........ RRR..... FFR.....
// ........ ..RRR... .FRRR...
// ........ ..R..... .FFFFF..
// ........ ..RRRR.R ..RRRFFR
// ........ .....RRR .....FFF

// i had a greedy that always would work but the 0/1 bfs is just too clean

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1740 KB Output isn't correct
2 Incorrect 0 ms 312 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Correct 6 ms 1356 KB Output is correct
5 Incorrect 4 ms 836 KB Output isn't correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Incorrect 1 ms 332 KB Output isn't correct
8 Correct 1 ms 332 KB Output is correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 3 ms 844 KB Output isn't correct
11 Correct 2 ms 588 KB Output is correct
12 Incorrect 5 ms 844 KB Output isn't correct
13 Incorrect 4 ms 844 KB Output isn't correct
14 Incorrect 4 ms 836 KB Output isn't correct
15 Incorrect 13 ms 2124 KB Output isn't correct
16 Incorrect 12 ms 1740 KB Output isn't correct
17 Incorrect 12 ms 1836 KB Output isn't correct
18 Correct 6 ms 1472 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 836 KB Output isn't correct
2 Incorrect 60 ms 13372 KB Output isn't correct
3 Incorrect 590 ms 113632 KB Output isn't correct
4 Incorrect 154 ms 23680 KB Output isn't correct
5 Incorrect 318 ms 86640 KB Output isn't correct
6 Correct 721 ms 98756 KB Output is correct
7 Incorrect 3 ms 844 KB Output isn't correct
8 Incorrect 3 ms 844 KB Output isn't correct
9 Incorrect 3 ms 708 KB Output isn't correct
10 Incorrect 1 ms 588 KB Output isn't correct
11 Incorrect 3 ms 836 KB Output isn't correct
12 Incorrect 1 ms 460 KB Output isn't correct
13 Incorrect 61 ms 13288 KB Output isn't correct
14 Incorrect 36 ms 7812 KB Output isn't correct
15 Incorrect 40 ms 8908 KB Output isn't correct
16 Incorrect 27 ms 5692 KB Output isn't correct
17 Incorrect 160 ms 34244 KB Output isn't correct
18 Incorrect 173 ms 33368 KB Output isn't correct
19 Incorrect 149 ms 23568 KB Output isn't correct
20 Incorrect 126 ms 27440 KB Output isn't correct
21 Incorrect 330 ms 68208 KB Output isn't correct
22 Incorrect 316 ms 86600 KB Output isn't correct
23 Incorrect 297 ms 62124 KB Output isn't correct
24 Incorrect 314 ms 74872 KB Output isn't correct
25 Incorrect 910 ms 123128 KB Output isn't correct
26 Correct 753 ms 116180 KB Output is correct
27 Correct 670 ms 106720 KB Output is correct
28 Correct 715 ms 98736 KB Output is correct
29 Correct 708 ms 95912 KB Output is correct
30 Correct 699 ms 99544 KB Output is correct
31 Incorrect 494 ms 56260 KB Output isn't correct
32 Incorrect 715 ms 101624 KB Output isn't correct