oj.uz

Submission #951523

# Submission time Handle Problem Language Result Execution time Memory
951523 2024-03-22T05:03:54 Z serpent_121 Tracks in the Snow (BOI13_tracks) C++17
61.6667 / 100
 1261 ms 396796 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <numeric>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;

int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

ll depth[4000][4000];

int main() {
    ll h,w; cin >> h >> w;
    ll map[h][w];
    for (int i = 0; i< h; i++) {
        for (int j = 0; j<w; j++) {
            char k; cin >> k;
            if (k=='.') map[i][j] = 0;
            else if (k=='R') map[i][j] = 1;
            else map[i][j] = 2;
        }
    }
    deque<pair<ll,ll>> q; 
    q.push_back({0,0});
    depth[0][0] = 1;
    ll maxdepth = 1;

    while (!q.empty()) {
        ll x= q.front().first; ll y = q.front().second; q.pop_front();
        for (int i = 0; i<4; i++) {
            if (x+dx[i]<w && x+dx[i]>=0 && y+dy[i]<h && y+dy[i]>=0 && map[x+dx[i]][y+dy[i]]!=0) {
                ll a = x+dx[i]; ll b = y+dy[i];
                if (map[a][b]==map[x][y] && depth[a][b]==0) {
                    q.push_front({a,b});
                    depth[a][b] = depth[x][y];
                }
                else {
                    if (depth[a][b]==0 || depth[a][b] > depth[x][y]+1) {
                        depth[a][b] = depth[x][y]+1; q.push_back({a,b});
                        maxdepth = max(maxdepth,depth[a][b]);
                    }
                }
            }
        }
    }

    cout << maxdepth;
}

Subtask #1
26.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 6456 KB Output isn't correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 12 ms 4700 KB Output is correct
5 Correct 7 ms 2660 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 4 ms 2396 KB Output is correct
11 Correct 3 ms 1884 KB Output is correct
12 Correct 8 ms 2908 KB Output is correct
13 Correct 6 ms 2652 KB Output is correct
14 Correct 5 ms 2652 KB Output is correct
15 Correct 20 ms 6100 KB Output is correct
16 Incorrect 23 ms 6476 KB Output isn't correct
17 Correct 18 ms 6232 KB Output is correct
18 Correct 13 ms 4700 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 860 KB Output isn't correct
2 Correct 96 ms 25428 KB Output is correct
3 Correct 778 ms 201172 KB Output is correct
4 Runtime error 232 ms 108112 KB Execution killed with signal 11
5 Correct 425 ms 129996 KB Output is correct
6 Correct 1261 ms 293460 KB Output is correct
7 Incorrect 2 ms 856 KB Output isn't correct
8 Incorrect 3 ms 1016 KB Output isn't correct
9 Incorrect 3 ms 860 KB Output isn't correct
10 Incorrect 2 ms 604 KB Output isn't correct
11 Incorrect 2 ms 860 KB Output isn't correct
12 Correct 2 ms 1372 KB Output is correct
13 Correct 108 ms 25568 KB Output is correct
14 Runtime error 80 ms 30800 KB Execution killed with signal 11
15 Correct 58 ms 21072 KB Output is correct
16 Incorrect 26 ms 6492 KB Output isn't correct
17 Correct 242 ms 60244 KB Output is correct
18 Correct 227 ms 75228 KB Output is correct
19 Runtime error 246 ms 108112 KB Execution killed with signal 11
20 Incorrect 130 ms 30816 KB Output isn't correct
21 Incorrect 428 ms 122432 KB Output isn't correct
22 Correct 416 ms 129996 KB Output is correct
23 Incorrect 482 ms 98528 KB Output isn't correct
24 Incorrect 412 ms 118544 KB Output isn't correct
25 Correct 1087 ms 266572 KB Output is correct
26 Correct 750 ms 318136 KB Output is correct
27 Correct 955 ms 319812 KB Output is correct
28 Correct 1220 ms 293884 KB Output is correct
29 Correct 1233 ms 290240 KB Output is correct
30 Runtime error 945 ms 396796 KB Execution killed with signal 11
31 Runtime error 543 ms 201392 KB Execution killed with signal 11
32 Correct 896 ms 290940 KB Output is correct