oj.uz

Submission #484934

# Submission time Handle Problem Language Result Execution time Memory
484934 2021-11-05T18:23:52 Z Olympia Tracks in the Snow (BOI13_tracks) C++17
82.5 / 100
 2000 ms 45360 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() {
    //freopen("milkorder.in", "r", stdin);
    //freopen("milkorder.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    priority_queue<pair<int, pair<int, int>>> q;
    grid.resize(n), hasVisited.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        hasVisited[i].resize(m);
        for (int j = 0; j < m; j++) {
            hasVisited[i][j] = false;
        }
    }
    q.push({0, {0, 0}});
    int myMax = 0;
    while (!q.empty()) {
        pair<int, int> loc = q.top().second;
        int dist = -q.top().first;
        myMax = max(myMax, dist);
        q.pop();
        if (hasVisited[loc.first][loc.second]) {
            continue;
        }
        hasVisited[loc.first][loc.second] = true;
        for (auto p: pos) {
            int dx = p.first;
            int dy = p.second;
            if (dx + loc.first >= 0 && dy + loc.second >= 0 && dx + loc.first < n && dy + loc.second < m
                && grid[loc.first + dx][loc.second + dy] != '.') {
                if (hasVisited[loc.first + dx][loc.second + dy]) {
                    myMax = max(myMax, dist + (grid[dx + loc.first][dy + loc.second] != grid[loc.first][loc.second]));
                    continue;
                }
                q.push(make_pair(-dist - (grid[dx + loc.first][dy + loc.second] != grid[loc.first][loc.second]),
                                 make_pair(loc.first + dx, loc.second + dy)));
            }
        }
    }
    cout << myMax;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 884 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 49 ms 1416 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 6 ms 428 KB Output is correct
11 Correct 14 ms 460 KB Output is correct
12 Correct 29 ms 616 KB Output is correct
13 Correct 4 ms 332 KB Output is correct
14 Correct 4 ms 448 KB Output is correct
15 Correct 57 ms 716 KB Output is correct
16 Correct 83 ms 908 KB Output is correct
17 Correct 26 ms 588 KB Output is correct
18 Correct 50 ms 1408 KB Output is correct

Subtask #2
52.5 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 163 ms 2320 KB Output is correct
3 Correct 463 ms 20496 KB Output is correct
4 Correct 113 ms 4940 KB Output is correct
5 Correct 147 ms 11328 KB Output is correct
6 Execution timed out 2085 ms 45272 KB Time limit exceeded
7 Correct 2 ms 716 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 7 ms 540 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 332 KB Output is correct
13 Correct 165 ms 2324 KB Output is correct
14 Correct 94 ms 1532 KB Output is correct
15 Correct 12 ms 1484 KB Output is correct
16 Correct 92 ms 1196 KB Output is correct
17 Correct 414 ms 5452 KB Output is correct
18 Correct 51 ms 5196 KB Output is correct
19 Correct 110 ms 4928 KB Output is correct
20 Correct 119 ms 4428 KB Output is correct
21 Correct 279 ms 11852 KB Output is correct
22 Correct 147 ms 11432 KB Output is correct
23 Correct 833 ms 10180 KB Output is correct
24 Correct 109 ms 11588 KB Output is correct
25 Correct 274 ms 20396 KB Output is correct
26 Execution timed out 2093 ms 15656 KB Time limit exceeded
27 Execution timed out 2098 ms 23700 KB Time limit exceeded
28 Execution timed out 2070 ms 45268 KB Time limit exceeded
29 Execution timed out 2098 ms 45360 KB Time limit exceeded
30 Execution timed out 2094 ms 44812 KB Time limit exceeded
31 Execution timed out 2091 ms 14692 KB Time limit exceeded
32 Execution timed out 2079 ms 22228 KB Time limit exceeded