oj.uz

Submission #763981

# Submission time Handle Problem Language Result Execution time Memory
763981 2023-06-23T04:26:26 Z yandabao Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 733 ms 122724 KB 
#include <iostream>
#include <vector>
#include <limits>
#include <map>
#include <algorithm>
#include <set>
#include <string>
#include <cmath>
#include <climits>
#include <string.h>
#include <fstream>
#include <stack>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vvi= vector<vector<int> >;
using vll = vector<long long>;
using vpi = vector<pair<int, int> >;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
//cin.tie(0)->sync_with_stdio(0);

int H, W;
vector<vector<char> > grid;
vvi depth;
int dx[4]{-1, 1, 0, 0}, dy[4]{0, 0, 1, -1};

int main(){
    cin >> H >> W;
    grid.rsz(H);
    depth.rsz(H);
    for (int i = 0; i < H; i++)
    {  
        grid[i].rsz(W);
        depth[i].rsz(W);
        string str; cin >> str;
        for (int j = 0; j < W; j++)
        {
            grid[i][j] = str[j];
        }
    }
    depth[0][0] = 1;
    deque<pair<int, int> > traverse;
    traverse.push_front(mp(0, 0));
    while(traverse.size() > 0){
        pair<int, int> curr = traverse.front(); traverse.pop_front();
        for (int i = 0; i < 4; i++)
        {
            int x = curr.f + dx[i];
            int y = curr.s + dy[i];
            if(x < 0 || x >= H || y < 0 || y >= W){
                continue;
            }
            if(grid[x][y] == '.' || depth[x][y] != 0){
                continue;
            }
            if(grid[x][y] != grid[curr.f][curr.s]){
                depth[x][y] = depth[curr.f][curr.s] + 1;
                traverse.push_back(mp(x, y));
            } else {
                depth[x][y] = depth[curr.f][curr.s];
                traverse.push_front(mp(x, y));
            }
        }
    }

    int maxV = -1;

    for (int i = 0; i < H; i++)
    {
        for (int j = 0; j < W; j++)
        {
            maxV = max(depth[i][j], maxV);
        }
    }
    cout << maxV;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1748 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 7 ms 1400 KB Output is correct
5 Correct 3 ms 696 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 5 ms 824 KB Output is correct
13 Correct 3 ms 692 KB Output is correct
14 Correct 3 ms 696 KB Output is correct
15 Correct 11 ms 1760 KB Output is correct
16 Correct 12 ms 1724 KB Output is correct
17 Correct 9 ms 1748 KB Output is correct
18 Correct 7 ms 1384 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Correct 53 ms 9548 KB Output is correct
3 Correct 438 ms 94512 KB Output is correct
4 Correct 99 ms 22352 KB Output is correct
5 Correct 221 ms 53392 KB Output is correct
6 Correct 726 ms 108800 KB Output is correct
7 Correct 3 ms 800 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 49 ms 9464 KB Output is correct
14 Correct 29 ms 5596 KB Output is correct
15 Correct 25 ms 6208 KB Output is correct
16 Correct 23 ms 4056 KB Output is correct
17 Correct 134 ms 24228 KB Output is correct
18 Correct 110 ms 23924 KB Output is correct
19 Correct 103 ms 22436 KB Output is correct
20 Correct 103 ms 20484 KB Output is correct
21 Correct 232 ms 55208 KB Output is correct
22 Correct 225 ms 53324 KB Output is correct
23 Correct 256 ms 45948 KB Output is correct
24 Correct 223 ms 53836 KB Output is correct
25 Correct 542 ms 94516 KB Output is correct
26 Correct 482 ms 122724 KB Output is correct
27 Correct 639 ms 108020 KB Output is correct
28 Correct 733 ms 108820 KB Output is correct
29 Correct 716 ms 106972 KB Output is correct
30 Correct 681 ms 108276 KB Output is correct
31 Correct 501 ms 61092 KB Output is correct
32 Correct 583 ms 108940 KB Output is correct