oj.uz

Submission #951525

# Submission time Handle Problem Language Result Execution time Memory
951525 2024-03-22T05:08:20 Z serpent_121 Tracks in the Snow (BOI13_tracks) C++17
46.25 / 100
 848 ms 340212 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();
        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];
                maxdepth = max(maxdepth,depth[a][b]);
                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});        
                    }
                }
            }
        }
    }

    cout << maxdepth;
}

Subtask #1
20.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 5212 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 9 ms 3916 KB Output is correct
5 Correct 3 ms 2396 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't 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 3 ms 1884 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Incorrect 8 ms 2652 KB Output isn't correct
13 Correct 3 ms 2396 KB Output is correct
14 Correct 3 ms 2396 KB Output is correct
15 Incorrect 15 ms 4956 KB Output isn't correct
16 Incorrect 17 ms 5320 KB Output isn't correct
17 Correct 12 ms 4952 KB Output is correct
18 Correct 8 ms 3928 KB Output is correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Correct 58 ms 20820 KB Output is correct
3 Correct 361 ms 167340 KB Output is correct
4 Runtime error 134 ms 89936 KB Execution killed with signal 11
5 Incorrect 203 ms 103152 KB Output isn't correct
6 Correct 848 ms 215152 KB Output is correct
7 Incorrect 1 ms 616 KB Output isn't correct
8 Incorrect 1 ms 872 KB Output isn't correct
9 Incorrect 1 ms 860 KB Output isn't correct
10 Incorrect 1 ms 600 KB Output isn't correct
11 Incorrect 1 ms 860 KB Output isn't correct
12 Incorrect 1 ms 1368 KB Output isn't correct
13 Correct 56 ms 20848 KB Output is correct
14 Incorrect 35 ms 13136 KB Output isn't correct
15 Correct 29 ms 15960 KB Output is correct
16 Incorrect 11 ms 5728 KB Output isn't correct
17 Correct 151 ms 48600 KB Output is correct
18 Correct 127 ms 55484 KB Output is correct
19 Runtime error 134 ms 89936 KB Execution killed with signal 11
20 Incorrect 55 ms 27492 KB Output isn't correct
21 Incorrect 210 ms 103488 KB Output isn't correct
22 Incorrect 207 ms 103344 KB Output isn't correct
23 Incorrect 249 ms 80736 KB Output isn't correct
24 Incorrect 196 ms 98108 KB Output isn't correct
25 Incorrect 645 ms 188256 KB Output isn't correct
26 Correct 449 ms 251484 KB Output is correct
27 Correct 576 ms 241512 KB Output is correct
28 Correct 818 ms 215580 KB Output is correct
29 Correct 831 ms 212296 KB Output is correct
30 Runtime error 473 ms 340212 KB Execution killed with signal 11
31 Runtime error 306 ms 190816 KB Execution killed with signal 11
32 Correct 592 ms 213492 KB Output is correct