oj.uz

Submission #745785

# Submission time Handle Problem Language Result Execution time Memory
745785 2023-05-21T07:43:10 Z darshitjn Tracks in the Snow (BOI13_tracks) C++14
81.3542 / 100
 1393 ms 232348 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[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 21 ms 2772 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 10 ms 4016 KB Execution killed with signal 11
5 Correct 4 ms 1108 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 356 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 10 ms 1108 KB Output is correct
13 Correct 4 ms 1108 KB Output is correct
14 Correct 4 ms 1108 KB Output is correct
15 Correct 18 ms 2900 KB Output is correct
16 Correct 21 ms 2852 KB Output is correct
17 Correct 17 ms 2644 KB Output is correct
18 Runtime error 9 ms 4052 KB Execution killed with signal 11

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 2004 KB Execution killed with signal 11
2 Correct 86 ms 15268 KB Output is correct
3 Correct 593 ms 163164 KB Output is correct
4 Correct 158 ms 38424 KB Output is correct
5 Correct 421 ms 88528 KB Output is correct
6 Correct 1393 ms 191200 KB Output is correct
7 Runtime error 2 ms 1876 KB Execution killed with signal 11
8 Runtime error 2 ms 1964 KB Execution killed with signal 11
9 Correct 5 ms 980 KB Output is correct
10 Correct 2 ms 724 KB Output is correct
11 Runtime error 2 ms 2004 KB Execution killed with signal 11
12 Correct 1 ms 468 KB Output is correct
13 Correct 85 ms 15188 KB Output is correct
14 Correct 46 ms 9300 KB Output is correct
15 Correct 40 ms 10156 KB Output is correct
16 Correct 45 ms 6160 KB Output is correct
17 Incorrect 233 ms 41684 KB Output isn't correct
18 Correct 171 ms 41132 KB Output is correct
19 Correct 157 ms 38372 KB Output is correct
20 Correct 143 ms 35112 KB Output is correct
21 Runtime error 286 ms 179164 KB Execution killed with signal 11
22 Correct 405 ms 88516 KB Output is correct
23 Correct 450 ms 76484 KB Output is correct
24 Runtime error 293 ms 175020 KB Execution killed with signal 11
25 Correct 892 ms 163196 KB Output is correct
26 Correct 890 ms 216740 KB Output is correct
27 Correct 1245 ms 232348 KB Output is correct
28 Correct 1321 ms 191200 KB Output is correct
29 Correct 1335 ms 186340 KB Output is correct
30 Correct 1241 ms 198316 KB Output is correct
31 Correct 1067 ms 100096 KB Output is correct
32 Correct 1073 ms 211896 KB Output is correct