oj.uz

Submission #1120640

# Submission time Handle Problem Language Result Execution time Memory
1120640 2024-11-28T08:27:15 Z HasanV11010238 Tracks in the Snow (BOI13_tracks) C++17
78.125 / 100
 2000 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);
    deque<int> q;
    di[st] = 0;
    q.push_back(st);
    while (!q.empty()){
        int x = q.front();
        q.pop_front();
        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:16: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]
   16 |             if (el[0] >= di.size()) return -1;
tracks.cpp: In function 'int main()':
tracks.cpp:50: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]
   50 |                 if (v.size() <= max(v1, v2)){
      |                     ~~~~~~~~~^~~~~~~~~~~~~~
tracks.cpp:67: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]
   67 |                 if (v.size() <= max(v1, v2)){
      |                     ~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 61692 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 109 ms 40872 KB Output is correct
5 Correct 12 ms 5968 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 3 ms 1616 KB Output is correct
9 Correct 2 ms 1024 KB Output is correct
10 Correct 11 ms 7248 KB Output is correct
11 Correct 26 ms 10976 KB Output is correct
12 Correct 52 ms 21920 KB Output is correct
13 Correct 15 ms 5968 KB Output is correct
14 Correct 12 ms 5968 KB Output is correct
15 Correct 135 ms 47412 KB Output is correct
16 Correct 164 ms 61768 KB Output is correct
17 Correct 76 ms 26960 KB Output is correct
18 Correct 109 ms 40916 KB Output is correct

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3672 KB Output is correct
2 Correct 437 ms 172536 KB Output is correct
3 Runtime error 1251 ms 1048576 KB Execution killed with signal 9
4 Correct 444 ms 192324 KB Output is correct
5 Correct 1255 ms 820204 KB Output is correct
6 Runtime error 1173 ms 1048576 KB Execution killed with signal 9
7 Correct 6 ms 3408 KB Output is correct
8 Correct 6 ms 3664 KB Output is correct
9 Correct 13 ms 7760 KB Output is correct
10 Correct 3 ms 2384 KB Output is correct
11 Correct 5 ms 2896 KB Output is correct
12 Correct 6 ms 2384 KB Output is correct
13 Correct 357 ms 172364 KB Output is correct
14 Correct 218 ms 100424 KB Output is correct
15 Correct 119 ms 64692 KB Output is correct
16 Correct 201 ms 91688 KB Output is correct
17 Correct 853 ms 434628 KB Output is correct
18 Correct 511 ms 252660 KB Output is correct
19 Correct 473 ms 192408 KB Output is correct
20 Correct 461 ms 254392 KB Output is correct
21 Correct 1042 ms 658384 KB Output is correct
22 Correct 1289 ms 820316 KB Output is correct
23 Correct 1878 ms 854584 KB Output is correct
24 Correct 1044 ms 635212 KB Output is correct
25 Execution timed out 2093 ms 1028928 KB Time limit exceeded
26 Runtime error 1092 ms 1048576 KB Execution killed with signal 9
27 Runtime error 1043 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1098 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1098 ms 1048576 KB Execution killed with signal 9
30 Runtime error 1139 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1282 ms 1048576 KB Execution killed with signal 9
32 Runtime error 1150 ms 1048576 KB Execution killed with signal 9