oj.uz

Submission #1120660

# Submission time Handle Problem Language Result Execution time Memory
1120660 2024-11-28T08:31:16 Z HasanV11010238 Tracks in the Snow (BOI13_tracks) C++17
78.125 / 100
 1746 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long long
#define INF 1000000000
vector<vector<vector<int>>> v;
int bfs(int n, int st){
    vector<int> di(n + 6, INF), us(n + 6, 0);
    deque<int> q;
    di[st] = 0;
    q.push_back(st);
    while (!q.empty()){
        int x = q.front();
        q.pop_front();
        if (us[x]) continue;
        us[x] = 1;
        for (auto el : v[x]){
            if (el[0] >= di.size()) return -1;
            if (di[el[0]] > di[x] + el[1]){
                di[el[0]] = di[x] + el[1];
                if (el[1] == 0){
                    q.push_front(el[0]);
                }
                else{
                    q.push_back(el[0]);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
        if (di[i] == INF) continue;
        ans = max(ans, di[i]);
    }
    return ans;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin>>n>>m;
    v.resize((n + 1) * (m + 1));
    vector<string> s(n);
    for (int i = 0; i < n; i++){
        cin>>s[i];
        for (int j = 0; j < m; j++){
            if (s[i][j] == '.') continue;
            int v1 = i * m + j;
            if (i != 0 && s[i - 1][j] != '.'){
                int v2 = (i - 1) * m + j;
                if (v.size() <= max(v1, v2)){
                    cout<<-1;
                    return 0;
                }
                int va;
                if (s[i][j] == s[i - 1][j]){
                    va = 0;
                }
                else{
                    va = 1;
                }
                v[v1].push_back({v2, va});
                v[v2].push_back({v1, va});
            }
            if (j != 0 && s[i][j - 1] != '.'){
                int v2 = i * m + j - 1;
                int va;
                if (v.size() <= max(v1, v2)){
                    cout<<-1;
                    return 0;
                }
                if (s[i][j] == s[i][j - 1]){
                    va = 0;
                }
                else{
                    va = 1;
                }
                v[v1].push_back({v2, va});
                v[v2].push_back({v1, va});
            }
        }
    }
    cout<<bfs(n * m, 0) + 1;
}

Compilation message

tracks.cpp: In function 'int bfs(int, int)':
tracks.cpp:18:23: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |             if (el[0] >= di.size()) return -1;
tracks.cpp: In function 'int main()':
tracks.cpp:52:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   52 |                 if (v.size() <= max(v1, v2)){
      |                     ~~~~~~~~~^~~~~~~~~~~~~~
tracks.cpp:69:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   69 |                 if (v.size() <= max(v1, v2)){
      |                     ~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 62792 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 89 ms 41532 KB Output is correct
5 Correct 10 ms 6224 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 6 ms 1632 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 13 ms 7504 KB Output is correct
11 Correct 23 ms 10948 KB Output is correct
12 Correct 52 ms 22368 KB Output is correct
13 Correct 11 ms 6224 KB Output is correct
14 Correct 11 ms 6224 KB Output is correct
15 Correct 126 ms 48200 KB Output is correct
16 Correct 164 ms 62776 KB Output is correct
17 Correct 61 ms 27952 KB Output is correct
18 Correct 90 ms 41408 KB Output is correct

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3920 KB Output is correct
2 Correct 382 ms 178512 KB Output is correct
3 Runtime error 1204 ms 1048576 KB Execution killed with signal 9
4 Correct 448 ms 207176 KB Output is correct
5 Correct 1208 ms 855628 KB Output is correct
6 Runtime error 1134 ms 1048576 KB Execution killed with signal 9
7 Correct 6 ms 3408 KB Output is correct
8 Correct 6 ms 3920 KB Output is correct
9 Correct 14 ms 8128 KB Output is correct
10 Correct 4 ms 2640 KB Output is correct
11 Correct 4 ms 3152 KB Output is correct
12 Correct 5 ms 2384 KB Output is correct
13 Correct 348 ms 178480 KB Output is correct
14 Correct 186 ms 103752 KB Output is correct
15 Correct 115 ms 68680 KB Output is correct
16 Correct 217 ms 94080 KB Output is correct
17 Correct 1002 ms 450636 KB Output is correct
18 Correct 474 ms 268340 KB Output is correct
19 Correct 441 ms 207176 KB Output is correct
20 Correct 434 ms 267776 KB Output is correct
21 Correct 1084 ms 694768 KB Output is correct
22 Correct 1230 ms 855624 KB Output is correct
23 Correct 1746 ms 884908 KB Output is correct
24 Correct 887 ms 674368 KB Output is correct
25 Runtime error 1093 ms 1048576 KB Execution killed with signal 9
26 Runtime error 1147 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1131 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1137 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1181 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1150 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1344 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1139 ms 1048576 KB Execution killed with signal 9