oj.uz

Submission #745781

# Submission time Handle Problem Language Result Execution time Memory
745781 2023-05-21T07:40:35 Z darshitjn Tracks in the Snow (BOI13_tracks) C++17
81.3542 / 100
 1206 ms 132648 KB 
#include <bits/stdc++.h>
using namespace std;
#define pi pair<int,int>

int32_t main(){
    int n,m; cin >> n >> m;
    string s[m];
    for(int i=0; i<m; 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
26.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2076 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Runtime error 8 ms 2516 KB Execution killed with signal 11
5 Correct 4 ms 852 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 304 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 724 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 8 ms 852 KB Output is correct
13 Correct 4 ms 784 KB Output is correct
14 Correct 4 ms 824 KB Output is correct
15 Correct 18 ms 2132 KB Output is correct
16 Correct 20 ms 2040 KB Output is correct
17 Correct 15 ms 2004 KB Output is correct
18 Runtime error 9 ms 2516 KB Execution killed with signal 11

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1620 KB Execution killed with signal 11
2 Correct 79 ms 10584 KB Output is correct
3 Correct 554 ms 98304 KB Output is correct
4 Correct 137 ms 25432 KB Output is correct
5 Correct 381 ms 51024 KB Output is correct
6 Correct 1206 ms 112268 KB Output is correct
7 Runtime error 2 ms 1748 KB Execution killed with signal 11
8 Runtime error 2 ms 1620 KB Execution killed with signal 11
9 Correct 4 ms 852 KB Output is correct
10 Correct 2 ms 608 KB Output is correct
11 Runtime error 2 ms 1632 KB Execution killed with signal 11
12 Correct 1 ms 468 KB Output is correct
13 Correct 78 ms 10588 KB Output is correct
14 Correct 44 ms 6652 KB Output is correct
15 Correct 41 ms 7244 KB Output is correct
16 Correct 42 ms 4364 KB Output is correct
17 Incorrect 203 ms 27148 KB Output isn't correct
18 Correct 162 ms 26920 KB Output is correct
19 Correct 146 ms 25412 KB Output is correct
20 Correct 127 ms 23740 KB Output is correct
21 Runtime error 228 ms 103036 KB Execution killed with signal 11
22 Correct 376 ms 51104 KB Output is correct
23 Correct 403 ms 43980 KB Output is correct
24 Runtime error 230 ms 100512 KB Execution killed with signal 11
25 Correct 746 ms 98224 KB Output is correct
26 Correct 798 ms 116276 KB Output is correct
27 Correct 1053 ms 132648 KB Output is correct
28 Correct 1176 ms 112004 KB Output is correct
29 Correct 1159 ms 109352 KB Output is correct
30 Correct 1096 ms 114652 KB Output is correct
31 Correct 801 ms 56292 KB Output is correct
32 Correct 960 ms 120460 KB Output is correct