oj.uz

Submission #1095215

# Submission time Handle Problem Language Result Execution time Memory
1095215 2024-10-01T15:07:51 Z InvMOD Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 906 ms 152268 KB 
#include<bits/stdc++.h>

using namespace std;

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

void solve()
{
    int n,m; cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c; cin >> c;
            a[i][j] = (c != '.' ? (c == 'F' ? 1 : 2) : 0);
        }
    }

    vector<vector<int>> mx_dif(n, vector<int>(m));

    function<bool(int,int)> init = [&](int x, int y){
        return x >= 0 && x < n && y >= 0 && y < m && a[x][y] != 0 && !mx_dif[x][y];
    };

    function<int(int,int)> id = [&](int x, int y){
        return x*m + y;
    };

    deque<int> dq;
    dq.push_back(0);
    mx_dif[0][0] = 1;

    while(!dq.empty()){
        int cur_id = dq.front(); dq.pop_front();

        int y = cur_id % m;
        int x = (cur_id - y) / m;
        for(int i = 0; i < 4; i++){
            int xx = dx[i] + x;
            int yy = dy[i] + y;
            if(init(xx, yy) && !mx_dif[xx][yy]){
                if(a[xx][yy] != a[x][y]){
                    mx_dif[xx][yy] = mx_dif[x][y] + 1;
                    dq.push_back(id(xx, yy));
                }
                else{
                    mx_dif[xx][yy] = mx_dif[x][y];
                    dq.push_front(id(xx, yy));
                }
            }
        }
    }

    int answer = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            answer = max(answer, mx_dif[i][j]);
        }
    }
    cout << answer <<"\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message

tracks.cpp: In function 'int32_t main()':
tracks.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 7 ms 1884 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 5 ms 1116 KB Output is correct
13 Correct 3 ms 1116 KB Output is correct
14 Correct 3 ms 1136 KB Output is correct
15 Correct 11 ms 2652 KB Output is correct
16 Correct 13 ms 2652 KB Output is correct
17 Correct 11 ms 2396 KB Output is correct
18 Correct 8 ms 1884 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1096 KB Output is correct
2 Correct 50 ms 14160 KB Output is correct
3 Correct 339 ms 141496 KB Output is correct
4 Correct 99 ms 33364 KB Output is correct
5 Correct 219 ms 79700 KB Output is correct
6 Correct 840 ms 148416 KB Output is correct
7 Correct 2 ms 1116 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 1116 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 53 ms 14296 KB Output is correct
14 Correct 27 ms 8280 KB Output is correct
15 Correct 23 ms 9320 KB Output is correct
16 Correct 28 ms 5980 KB Output is correct
17 Correct 139 ms 36296 KB Output is correct
18 Correct 105 ms 35636 KB Output is correct
19 Correct 116 ms 33496 KB Output is correct
20 Correct 77 ms 30800 KB Output is correct
21 Correct 207 ms 82512 KB Output is correct
22 Correct 224 ms 79816 KB Output is correct
23 Correct 286 ms 68820 KB Output is correct
24 Correct 219 ms 80536 KB Output is correct
25 Correct 452 ms 141652 KB Output is correct
26 Correct 506 ms 133648 KB Output is correct
27 Correct 691 ms 152268 KB Output is correct
28 Correct 906 ms 148296 KB Output is correct
29 Correct 894 ms 147416 KB Output is correct
30 Correct 766 ms 146772 KB Output is correct
31 Correct 602 ms 90960 KB Output is correct
32 Correct 584 ms 147900 KB Output is correct