oj.uz

Submission #745788

# Submission time Handle Problem Language Result Execution time Memory
745788 2023-05-21T07:46:49 Z darshitjn Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1268 ms 227584 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int,int>

int32_t main(){
    int n,m; cin >> n >> m;
    string s[n];
    for(int i=0; i<n; i++){
        cin >> s[i];
    }

    vector <pi> v = {{1,0},{0,1},{-1,0},{0,-1}};

    if(s[0][0]=='.'){cout << 0 << endl; return 0;}
    int ans = 1;
    vector <vector<bool>> vis(n,vector<bool>(m,0));
    vis[0][0] = 1;
    deque <pi> q;
    q.push_front({0,0});
    vector <vector<int>> d(n,vector<int>(m,0));
    d[0][0] = 1;
    function <bool(int,int)> ok = [&](int x,int y){
        if(x<0 || x>n-1 || y<0 || y>m-1){return false;}
        if(vis[x][y]){return false;}
        return (s[x][y] != '.');
    };

    function <void(pi)> process = [&](pi k){
        for(auto e:v){
            int x = e.first+k.first;
            int y = e.second+k.second;
            if(ok(x,y)){
                vis[x][y] = 1;
                d[x][y] = d[k.first][k.second];
                if(s[x][y] != s[k.first][k.second]){
                    q.push_back({x,y});
                    d[x][y]++;
                }else{
                    q.push_front({x,y});
                }
            }
        }
    };

    while(q.size()){
        auto k = q.front();
        q.pop_front();
        ans = max(ans,d[k.first][k.second]);
        process(k);
    }

    cout << ans << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2864 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 12 ms 2132 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 7 ms 1108 KB Output is correct
13 Correct 4 ms 1108 KB Output is correct
14 Correct 6 ms 1064 KB Output is correct
15 Correct 18 ms 2868 KB Output is correct
16 Correct 20 ms 2864 KB Output is correct
17 Correct 14 ms 2644 KB Output is correct
18 Correct 11 ms 2208 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1120 KB Output is correct
2 Correct 82 ms 15268 KB Output is correct
3 Correct 583 ms 158160 KB Output is correct
4 Correct 144 ms 37440 KB Output is correct
5 Correct 393 ms 83460 KB Output is correct
6 Correct 1266 ms 186344 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 82 ms 15184 KB Output is correct
14 Correct 47 ms 9220 KB Output is correct
15 Correct 42 ms 10188 KB Output is correct
16 Correct 40 ms 6108 KB Output is correct
17 Correct 212 ms 40312 KB Output is correct
18 Correct 170 ms 39860 KB Output is correct
19 Correct 143 ms 37356 KB Output is correct
20 Correct 131 ms 34400 KB Output is correct
21 Correct 334 ms 86652 KB Output is correct
22 Correct 387 ms 83468 KB Output is correct
23 Correct 391 ms 71720 KB Output is correct
24 Correct 351 ms 85196 KB Output is correct
25 Correct 811 ms 158100 KB Output is correct
26 Correct 845 ms 211728 KB Output is correct
27 Correct 1143 ms 227584 KB Output is correct
28 Correct 1268 ms 186140 KB Output is correct
29 Correct 1252 ms 181428 KB Output is correct
30 Correct 1184 ms 193268 KB Output is correct
31 Correct 901 ms 95180 KB Output is correct
32 Correct 1014 ms 206788 KB Output is correct