oj.uz

Submission #892442

# Submission time Handle Problem Language Result Execution time Memory
892442 2023-12-25T10:50:01 Z tnknguyen_ Tracks in the Snow (BOI13_tracks) C++14
19.7917 / 100
 943 ms 257992 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;
}

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 21340 KB Output isn't correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Incorrect 1 ms 6492 KB Output isn't correct
4 Correct 9 ms 21340 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 6492 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 11352 KB Output is correct
12 Incorrect 7 ms 15964 KB Output isn't correct
13 Incorrect 6 ms 16220 KB Output isn't correct
14 Incorrect 5 ms 16220 KB Output isn't correct
15 Incorrect 13 ms 22108 KB Output isn't correct
16 Incorrect 12 ms 21592 KB Output isn't correct
17 Incorrect 11 ms 21852 KB Output isn't correct
18 Correct 8 ms 21340 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 140892 KB Output isn't correct
2 Incorrect 72 ms 59016 KB Output isn't correct
3 Incorrect 742 ms 242164 KB Output isn't correct
4 Incorrect 179 ms 93120 KB Output isn't correct
5 Incorrect 499 ms 181988 KB Output isn't correct
6 Correct 728 ms 202972 KB Output is correct
7 Incorrect 21 ms 141912 KB Output isn't correct
8 Incorrect 21 ms 140892 KB Output isn't correct
9 Incorrect 3 ms 6888 KB Output isn't correct
10 Incorrect 2 ms 4700 KB Output isn't correct
11 Incorrect 22 ms 141368 KB Output isn't correct
12 Incorrect 2 ms 11100 KB Output isn't correct
13 Incorrect 71 ms 59116 KB Output isn't correct
14 Incorrect 39 ms 42064 KB Output isn't correct
15 Incorrect 47 ms 46932 KB Output isn't correct
16 Incorrect 27 ms 22412 KB Output isn't correct
17 Incorrect 188 ms 103856 KB Output isn't correct
18 Incorrect 230 ms 108700 KB Output isn't correct
19 Incorrect 173 ms 93264 KB Output isn't correct
20 Incorrect 159 ms 91080 KB Output isn't correct
21 Incorrect 438 ms 180000 KB Output isn't correct
22 Incorrect 488 ms 181868 KB Output isn't correct
23 Incorrect 372 ms 141124 KB Output isn't correct
24 Incorrect 437 ms 181064 KB Output isn't correct
25 Incorrect 943 ms 257992 KB Output isn't correct
26 Correct 708 ms 217496 KB Output is correct
27 Correct 672 ms 214352 KB Output is correct
28 Correct 697 ms 202944 KB Output is correct
29 Correct 705 ms 200212 KB Output is correct
30 Correct 674 ms 205512 KB Output is correct
31 Incorrect 470 ms 154840 KB Output isn't correct
32 Incorrect 729 ms 209820 KB Output isn't correct