oj.uz

Submission #856952

# Submission time Handle Problem Language Result Execution time Memory
856952 2023-10-05T01:12:03 Z teesla Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1061 ms 135836 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4005;
typedef pair<int,int> ii;
typedef pair<int, ii> iii;

int adj[maxn][maxn], vis[maxn][maxn];
int vx[4] = {0,1,0,-1}, vy[4] = {1,0,-1,0};
int h,w;


int dijkstra(){

    queue<ii> zero,um;

    zero.push({h,w});
    vis[h][w] = 1;
    int res = 0;

    while(!zero.empty()){

        res++;

        while(!zero.empty()){

            auto [a,b] = zero.front();
            zero.pop();

            if(vis[a][b] < res) continue;

            for(int i=0; i<4; i++){

                int xx = a + vx[i], yy = b + vy[i];

                if(adj[xx][yy] == 0) continue;

                int val = vis[a][b];

                if(adj[xx][yy] != adj[a][b]){
                    val ++;
                }

                if( vis[xx][yy] != 0 and vis[xx][yy] <= val) continue;

                vis[xx][yy] = val;

                if(val == res) zero.push({xx,yy});
                else um.push({xx,yy});
            }

        }



        swap(zero,um);
    }

    
    return res;
}

int main(){

     cin >> h >> w;


    for(int i=1; i<=h; i++){

        string s; cin >> s;

        for(int j =0; j<w; j++){

            int val = 0;
            if(s[j] == 'R') val = 1;
            else if(s[j] == 'F') val = 2;

            adj[i][j+1] = val;
        }

    }


    cout << dijkstra() << endl;
    return 0;
}

Compilation message

tracks.cpp: In function 'int dijkstra()':
tracks.cpp:26:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |             auto [a,b] = zero.front();
      |                  ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15192 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 9 ms 14940 KB Output is correct
5 Correct 4 ms 9812 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 4 ms 9052 KB Output is correct
11 Correct 3 ms 9152 KB Output is correct
12 Correct 7 ms 10072 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 15 ms 14940 KB Output is correct
16 Correct 17 ms 15020 KB Output is correct
17 Correct 13 ms 15448 KB Output is correct
18 Correct 10 ms 14940 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 79276 KB Output is correct
2 Correct 62 ms 32804 KB Output is correct
3 Correct 483 ms 105044 KB Output is correct
4 Correct 99 ms 53964 KB Output is correct
5 Correct 220 ms 82924 KB Output is correct
6 Correct 997 ms 135820 KB Output is correct
7 Correct 19 ms 79960 KB Output is correct
8 Correct 14 ms 79452 KB Output is correct
9 Correct 3 ms 4492 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 13 ms 81496 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 60 ms 32708 KB Output is correct
14 Correct 38 ms 23636 KB Output is correct
15 Correct 29 ms 28248 KB Output is correct
16 Correct 28 ms 12636 KB Output is correct
17 Correct 153 ms 51540 KB Output is correct
18 Correct 110 ms 58448 KB Output is correct
19 Correct 98 ms 54096 KB Output is correct
20 Correct 90 ms 45652 KB Output is correct
21 Correct 234 ms 83744 KB Output is correct
22 Correct 215 ms 82840 KB Output is correct
23 Correct 293 ms 69340 KB Output is correct
24 Correct 221 ms 81300 KB Output is correct
25 Correct 576 ms 125776 KB Output is correct
26 Correct 657 ms 113296 KB Output is correct
27 Correct 722 ms 127580 KB Output is correct
28 Correct 1061 ms 135836 KB Output is correct
29 Correct 966 ms 134428 KB Output is correct
30 Correct 846 ms 133504 KB Output is correct
31 Correct 710 ms 103508 KB Output is correct
32 Correct 630 ms 126652 KB Output is correct