oj.uz

Submission #951529

# Submission time Handle Problem Language Result Execution time Memory
951529 2024-03-22T05:11:52 Z serpent_121 Tracks in the Snow (BOI13_tracks) C++17
61.6667 / 100
 744 ms 342564 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};

int depth[4000][4000];

int main() {
    iostream::sync_with_stdio(false);
	cin.tie(0);
    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;
    int maxdepth = 1;

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

    std::cout << maxdepth;
}

Subtask #1
26.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5212 KB Output isn't correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 6 ms 3932 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 4 ms 1884 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 5 ms 2652 KB Output is correct
13 Correct 5 ms 2392 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Correct 11 ms 4956 KB Output is correct
16 Incorrect 13 ms 5208 KB Output isn't correct
17 Correct 11 ms 4956 KB Output is correct
18 Correct 7 ms 3932 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 860 KB Output isn't correct
2 Correct 57 ms 20928 KB Output is correct
3 Correct 341 ms 167148 KB Output is correct
4 Runtime error 132 ms 90024 KB Execution killed with signal 11
5 Correct 203 ms 103176 KB Output is correct
6 Correct 709 ms 215456 KB Output is correct
7 Incorrect 1 ms 668 KB Output isn't correct
8 Incorrect 1 ms 860 KB Output isn't correct
9 Incorrect 2 ms 856 KB Output isn't correct
10 Incorrect 1 ms 604 KB Output isn't correct
11 Incorrect 1 ms 860 KB Output isn't correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 52 ms 20984 KB Output is correct
14 Incorrect 31 ms 13136 KB Output isn't correct
15 Correct 29 ms 15964 KB Output is correct
16 Incorrect 11 ms 5724 KB Output isn't correct
17 Correct 137 ms 48572 KB Output is correct
18 Correct 125 ms 55380 KB Output is correct
19 Runtime error 140 ms 89940 KB Execution killed with signal 11
20 Incorrect 49 ms 27380 KB Output isn't correct
21 Incorrect 195 ms 103252 KB Output isn't correct
22 Correct 203 ms 102992 KB Output is correct
23 Incorrect 221 ms 80724 KB Output isn't correct
24 Incorrect 215 ms 97948 KB Output isn't correct
25 Correct 677 ms 188440 KB Output is correct
26 Correct 440 ms 252108 KB Output is correct
27 Correct 563 ms 241408 KB Output is correct
28 Correct 744 ms 215372 KB Output is correct
29 Correct 704 ms 212412 KB Output is correct
30 Runtime error 442 ms 342564 KB Execution killed with signal 11
31 Runtime error 333 ms 191020 KB Execution killed with signal 11
32 Correct 476 ms 213424 KB Output is correct