oj.uz

Submission #856951

# Submission time Handle Problem Language Result Execution time Memory
856951 2023-10-05T00:58:16 Z teesla Tracks in the Snow (BOI13_tracks) C++14
84.6875 / 100
 2000 ms 148136 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(){

    priority_queue<iii, vector<iii> , greater<iii>> q;
    vis[h][w] = 1;

    q.push({1,{h,w}});
    int maior = 1;

    while(!q.empty()){

        auto [a,b] = q.top();
        auto [x,y] = b;
        q.pop();

        if(vis[x][y] < a) continue;
        maior = max(maior, a);

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

            int xx = x + vx[i], yy = y + vy[i];
            if(adj[xx][yy] == 0) continue;

            int val = a;

            if(adj[x][y] != adj[xx][yy]) val += 1;

            if(vis[xx][yy] != 0 and vis[xx][yy] <= val) continue;
            vis[xx][yy] = val;
            q.push({val, {xx,yy}});
        }
    }
    return maior;
}

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:22:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |         auto [a,b] = q.top();
      |              ^
tracks.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         auto [x,y] = b;
      |              ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15148 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 28 ms 15132 KB Output is correct
5 Correct 5 ms 9816 KB Output is correct
6 Correct 1 ms 4440 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 7 ms 9300 KB Output is correct
11 Correct 8 ms 9308 KB Output is correct
12 Correct 17 ms 9932 KB Output is correct
13 Correct 5 ms 9820 KB Output is correct
14 Correct 5 ms 9820 KB Output is correct
15 Correct 35 ms 14788 KB Output is correct
16 Correct 46 ms 15444 KB Output is correct
17 Correct 22 ms 14940 KB Output is correct
18 Correct 28 ms 15128 KB Output is correct

Subtask #2
54.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 79448 KB Output is correct
2 Correct 126 ms 32772 KB Output is correct
3 Correct 495 ms 105028 KB Output is correct
4 Correct 145 ms 54100 KB Output is correct
5 Correct 219 ms 82808 KB Output is correct
6 Execution timed out 2033 ms 147436 KB Time limit exceeded
7 Correct 13 ms 80020 KB Output is correct
8 Correct 14 ms 79452 KB Output is correct
9 Correct 5 ms 4700 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 13 ms 81324 KB Output is correct
12 Correct 2 ms 7004 KB Output is correct
13 Correct 121 ms 32852 KB Output is correct
14 Correct 69 ms 23632 KB Output is correct
15 Correct 29 ms 28248 KB Output is correct
16 Correct 62 ms 12708 KB Output is correct
17 Correct 307 ms 51540 KB Output is correct
18 Correct 109 ms 58452 KB Output is correct
19 Correct 150 ms 54232 KB Output is correct
20 Correct 121 ms 45652 KB Output is correct
21 Correct 298 ms 83920 KB Output is correct
22 Correct 220 ms 83144 KB Output is correct
23 Correct 597 ms 69536 KB Output is correct
24 Correct 220 ms 81088 KB Output is correct
25 Correct 536 ms 125896 KB Output is correct
26 Correct 1323 ms 113664 KB Output is correct
27 Execution timed out 2021 ms 127860 KB Time limit exceeded
28 Execution timed out 2059 ms 148136 KB Time limit exceeded
29 Execution timed out 2106 ms 138224 KB Time limit exceeded
30 Execution timed out 2045 ms 132976 KB Time limit exceeded
31 Execution timed out 2031 ms 103688 KB Time limit exceeded
32 Execution timed out 2047 ms 126380 KB Time limit exceeded