oj.uz

Submission #892441

# Submission time Handle Problem Language Result Execution time Memory
892441 2023-12-25T10:48:45 Z tnknguyen_ Tracks in the Snow (BOI13_tracks) C++14
19.7917 / 100
 962 ms 265892 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] && a[u][v] != -1){
                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 13 ms 21596 KB Output isn't correct
2 Incorrect 1 ms 6612 KB Output isn't correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Correct 9 ms 21576 KB Output is correct
5 Incorrect 5 ms 16472 KB Output isn't correct
6 Incorrect 1 ms 6612 KB Output isn't correct
7 Incorrect 1 ms 6492 KB Output isn't correct
8 Correct 1 ms 6488 KB Output is correct
9 Incorrect 2 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 5 ms 15960 KB Output isn't correct
13 Incorrect 8 ms 16220 KB Output isn't correct
14 Incorrect 5 ms 16264 KB Output isn't correct
15 Incorrect 13 ms 22220 KB Output isn't correct
16 Incorrect 13 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 27 ms 141152 KB Output isn't correct
2 Incorrect 75 ms 59988 KB Output isn't correct
3 Incorrect 750 ms 250544 KB Output isn't correct
4 Incorrect 182 ms 95328 KB Output isn't correct
5 Incorrect 489 ms 186484 KB Output isn't correct
6 Correct 735 ms 211100 KB Output is correct
7 Incorrect 22 ms 141904 KB Output isn't correct
8 Incorrect 25 ms 141140 KB Output isn't correct
9 Incorrect 3 ms 6744 KB Output isn't correct
10 Incorrect 2 ms 4700 KB Output isn't correct
11 Incorrect 23 ms 141588 KB Output isn't correct
12 Incorrect 2 ms 11236 KB Output isn't correct
13 Incorrect 80 ms 60172 KB Output isn't correct
14 Incorrect 39 ms 42832 KB Output isn't correct
15 Incorrect 47 ms 47800 KB Output isn't correct
16 Incorrect 27 ms 22864 KB Output isn't correct
17 Incorrect 192 ms 106164 KB Output isn't correct
18 Incorrect 227 ms 110976 KB Output isn't correct
19 Incorrect 182 ms 95168 KB Output isn't correct
20 Incorrect 158 ms 93020 KB Output isn't correct
21 Incorrect 437 ms 184768 KB Output isn't correct
22 Incorrect 510 ms 186576 KB Output isn't correct
23 Incorrect 369 ms 145480 KB Output isn't correct
24 Incorrect 445 ms 185780 KB Output isn't correct
25 Incorrect 962 ms 265892 KB Output isn't correct
26 Correct 673 ms 223588 KB Output is correct
27 Correct 672 ms 222660 KB Output is correct
28 Correct 713 ms 211240 KB Output is correct
29 Correct 710 ms 208684 KB Output is correct
30 Correct 695 ms 205316 KB Output is correct
31 Incorrect 434 ms 154900 KB Output isn't correct
32 Incorrect 732 ms 209664 KB Output isn't correct