oj.uz

Submission #745777

# Submission time Handle Problem Language Result Execution time Memory
745777 2023-05-21T07:37:37 Z darshitjn Tracks in the Snow (BOI13_tracks) C++17
81.3542 / 100
 1136 ms 145808 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,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]++;
                    ans = max(ans,d[x][y]);
                }else{
                    q.push_front({x,y});
                }
            }
        }
    };

    while(q.size()){
        auto k = q.front();
        q.pop_front();
        process(k);
    }

    cout << ans << endl;
}

Subtask #1
26.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2004 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 13 ms 2516 KB Execution killed with signal 11
5 Correct 5 ms 824 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 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 7 ms 852 KB Output is correct
13 Correct 7 ms 896 KB Output is correct
14 Correct 5 ms 852 KB Output is correct
15 Correct 21 ms 2048 KB Output is correct
16 Correct 21 ms 2092 KB Output is correct
17 Correct 15 ms 2016 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 87 ms 10644 KB Output is correct
3 Correct 579 ms 111124 KB Output is correct
4 Correct 140 ms 26444 KB Output is correct
5 Correct 395 ms 57084 KB Output is correct
6 Correct 1131 ms 125256 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 564 KB Output is correct
11 Runtime error 2 ms 1716 KB Execution killed with signal 11
12 Correct 2 ms 472 KB Output is correct
13 Correct 77 ms 10640 KB Output is correct
14 Correct 47 ms 6640 KB Output is correct
15 Correct 38 ms 7308 KB Output is correct
16 Correct 37 ms 4308 KB Output is correct
17 Incorrect 203 ms 28416 KB Output isn't correct
18 Correct 161 ms 28156 KB Output is correct
19 Correct 135 ms 26344 KB Output is correct
20 Correct 129 ms 24336 KB Output is correct
21 Runtime error 235 ms 109252 KB Execution killed with signal 11
22 Correct 386 ms 57172 KB Output is correct
23 Correct 389 ms 48884 KB Output is correct
24 Runtime error 226 ms 106532 KB Execution killed with signal 11
25 Correct 728 ms 111236 KB Output is correct
26 Correct 757 ms 125444 KB Output is correct
27 Correct 1036 ms 145808 KB Output is correct
28 Correct 1136 ms 125164 KB Output is correct
29 Correct 1111 ms 122692 KB Output is correct
30 Correct 1062 ms 128016 KB Output is correct
31 Correct 801 ms 64588 KB Output is correct
32 Correct 942 ms 135408 KB Output is correct