oj.uz

Submission #484945

# Submission time Handle Problem Language Result Execution time Memory
484945 2021-11-05T18:56:21 Z Olympia Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 937 ms 312216 KB 
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>

using namespace std;
vector<vector<bool>> hasVisited;
vector<string> grid;
vector<pair<int, int>> pos = {{0,  1},
                              {-1, 0},
                              {0,  -1},
                              {1,  0}};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    deque<pair<int, pair<int, int>>> q;
    grid.resize(n), hasVisited.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        hasVisited[i].assign(m, false);
    }
    q.push_back({1, {0, 0}});
    int myMax = 0;
    while (!q.empty()) {
        pair<int, int> loc = q.front().second;
        int dist = q.front().first;
        q.pop_front();
        if (hasVisited[loc.first][loc.second]) {
            continue;
        }
        myMax = max(myMax, dist);
        hasVisited[loc.first][loc.second] = true;
        for (auto p: pos) {
            int nx = loc.first + p.first;
            int ny = loc.second + p.second;
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && grid[nx][ny] != '.') {
                if (grid[nx][ny] != grid[loc.first][loc.second]) {
                    q.push_back(make_pair(dist + 1, make_pair(nx, ny)));
                } else {
                    q.push_front(make_pair(dist, make_pair(nx, ny)));
                }
            }
        }
    }
    cout << myMax;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 972 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 9 ms 1252 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 3 ms 332 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 6 ms 588 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 12 ms 716 KB Output is correct
16 Correct 16 ms 972 KB Output is correct
17 Correct 8 ms 588 KB Output is correct
18 Correct 8 ms 1228 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 41 ms 2252 KB Output is correct
3 Correct 196 ms 20436 KB Output is correct
4 Correct 45 ms 5060 KB Output is correct
5 Correct 145 ms 11460 KB Output is correct
6 Correct 856 ms 72196 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 716 KB Output is correct
12 Correct 1 ms 260 KB Output is correct
13 Correct 44 ms 2316 KB Output is correct
14 Correct 24 ms 1484 KB Output is correct
15 Correct 11 ms 1580 KB Output is correct
16 Correct 22 ms 1100 KB Output is correct
17 Correct 104 ms 5392 KB Output is correct
18 Correct 46 ms 5232 KB Output is correct
19 Correct 43 ms 4880 KB Output is correct
20 Correct 48 ms 4556 KB Output is correct
21 Correct 117 ms 11852 KB Output is correct
22 Correct 142 ms 11464 KB Output is correct
23 Correct 213 ms 10060 KB Output is correct
24 Correct 101 ms 11468 KB Output is correct
25 Correct 236 ms 20428 KB Output is correct
26 Correct 784 ms 312216 KB Output is correct
27 Correct 813 ms 179120 KB Output is correct
28 Correct 927 ms 72356 KB Output is correct
29 Correct 870 ms 68152 KB Output is correct
30 Correct 937 ms 104304 KB Output is correct
31 Correct 754 ms 15468 KB Output is correct
32 Correct 759 ms 155848 KB Output is correct