oj.uz

Submission #892439

# Submission time Handle Problem Language Result Execution time Memory
892439 2023-12-25T10:47:47 Z tnknguyen_ Tracks in the Snow (BOI13_tracks) C++14
19.7917 / 100
 946 ms 273620 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
/**
* IDEA:
*/

const int sz = 4e3 + 5;
int m, n;
int a[sz][sz], vi[sz][sz], d[sz][sz];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

bool valid(int x, int y){
    return (x >= 1 && x <= m && y >= 1 && y <= n);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("main.inp","r",stdin);
    // freopen("main.out","w",stdout);

    cin>>m>>n;

    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            char c;
            cin>>c;
            if(c == '.'){
                a[i][j] == -1;
            }
            if(c == 'F'){
                a[i][j] = 1;
            }
            else{
                a[i][j] = 2;
            }
        }
    }

    deque<pair<int,int>> q;
    q.push_front({1, 1});
    vi[1][1] = 1;
    d[1][1] = 1;

    int ans = 0;
    while(q.size()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop_front();

        ans = max(ans, d[x][y]);

        for(int i=0;i<4;++i){
            int u = x + dx[i];
            int v = y + dy[i];
            int c = (a[x][y] != a[u][v]);
            if(valid(u, v) && !vi[u][v]){
                d[u][v] = d[x][y] + c;
                vi[u][v] = 1;
                if(!c){
                    q.push_front({u, v});
                }
                else{
                    q.push_back({u, v});
                }
            }
        }
    }

    cout<<ans;

    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:33:25: warning: statement has no effect [-Wunused-value]
   33 |                 a[i][j] == -1;
      |                 ~~~~~~~~^~~~~

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21596 KB Output isn't correct
2 Incorrect 1 ms 6604 KB Output isn't correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Correct 8 ms 21556 KB Output is correct
5 Incorrect 5 ms 16220 KB Output isn't correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Incorrect 1 ms 6488 KB Output isn't correct
8 Correct 1 ms 6492 KB Output is correct
9 Incorrect 1 ms 6748 KB Output isn't correct
10 Incorrect 4 ms 13916 KB Output isn't correct
11 Correct 3 ms 11356 KB Output is correct
12 Incorrect 6 ms 16144 KB Output isn't correct
13 Incorrect 5 ms 16220 KB Output isn't correct
14 Incorrect 5 ms 16220 KB Output isn't correct
15 Incorrect 12 ms 22228 KB Output isn't correct
16 Incorrect 12 ms 21596 KB Output isn't correct
17 Incorrect 12 ms 22108 KB Output isn't correct
18 Correct 8 ms 21596 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 141140 KB Output isn't correct
2 Incorrect 74 ms 60500 KB Output isn't correct
3 Incorrect 753 ms 257924 KB Output isn't correct
4 Incorrect 187 ms 96848 KB Output isn't correct
5 Incorrect 478 ms 190632 KB Output isn't correct
6 Correct 702 ms 218692 KB Output is correct
7 Incorrect 21 ms 142172 KB Output isn't correct
8 Incorrect 21 ms 141184 KB Output isn't correct
9 Incorrect 3 ms 6864 KB Output isn't correct
10 Incorrect 2 ms 4688 KB Output isn't correct
11 Incorrect 23 ms 141404 KB Output isn't correct
12 Incorrect 2 ms 11100 KB Output isn't correct
13 Incorrect 71 ms 60616 KB Output isn't correct
14 Incorrect 38 ms 43068 KB Output isn't correct
15 Incorrect 47 ms 47956 KB Output isn't correct
16 Incorrect 26 ms 22876 KB Output isn't correct
17 Incorrect 200 ms 108208 KB Output isn't correct
18 Incorrect 224 ms 112592 KB Output isn't correct
19 Incorrect 174 ms 96860 KB Output isn't correct
20 Incorrect 154 ms 94536 KB Output isn't correct
21 Incorrect 441 ms 188988 KB Output isn't correct
22 Incorrect 487 ms 190580 KB Output isn't correct
23 Incorrect 351 ms 148868 KB Output isn't correct
24 Incorrect 438 ms 190092 KB Output isn't correct
25 Incorrect 946 ms 273620 KB Output isn't correct
26 Correct 679 ms 229408 KB Output is correct
27 Correct 623 ms 229748 KB Output is correct
28 Correct 691 ms 218564 KB Output is correct
29 Correct 694 ms 216144 KB Output is correct
30 Correct 683 ms 220044 KB Output is correct
31 Incorrect 452 ms 164936 KB Output isn't correct
32 Incorrect 764 ms 225376 KB Output isn't correct