oj.uz

Submission #484931

# Submission time Handle Problem Language Result Execution time Memory
484931 2021-11-05T18:16:39 Z Olympia Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 45248 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;
int main() {
    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;
        //cout << dist << " " << loc.first << " " << loc.second << endl;
        myMax = max(myMax, dist);
        q.pop();
        if (hasVisited[loc.first][loc.second]) {
            continue;
        }
        hasVisited[loc.first][loc.second] = true;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (abs(dx) + abs(dy) == 1 && dx + loc.first >= 0 && dy + loc.second >= 0 && dx + loc.first < n && dy + loc.second < m
                && grid[loc.first + dx][loc.second + dy] != '.' && !hasVisited[loc.first + dx][loc.second + dy]) {
                    int new_dist = -dist - (grid[dx + loc.first][dy + loc.second] != grid[loc.first][loc.second]);
                    q.push(make_pair(new_dist, make_pair(loc.first + dx, loc.second + dy)));
                }
            }
        }
    }
    cout << myMax;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 908 KB Output isn't correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Incorrect 52 ms 1368 KB Output isn't correct
5 Incorrect 5 ms 332 KB Output isn't correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Incorrect 2 ms 332 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 6 ms 332 KB Output isn't correct
11 Incorrect 15 ms 568 KB Output isn't correct
12 Incorrect 31 ms 608 KB Output isn't correct
13 Incorrect 5 ms 332 KB Output isn't correct
14 Incorrect 5 ms 332 KB Output isn't correct
15 Incorrect 60 ms 800 KB Output isn't correct
16 Incorrect 93 ms 908 KB Output isn't correct
17 Incorrect 29 ms 588 KB Output isn't correct
18 Incorrect 53 ms 1420 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 588 KB Output isn't correct
2 Incorrect 179 ms 2324 KB Output isn't correct
3 Incorrect 508 ms 20468 KB Output isn't correct
4 Incorrect 118 ms 4940 KB Output isn't correct
5 Incorrect 166 ms 11432 KB Output isn't correct
6 Execution timed out 2086 ms 45228 KB Time limit exceeded
7 Incorrect 2 ms 716 KB Output isn't correct
8 Incorrect 2 ms 588 KB Output isn't correct
9 Incorrect 8 ms 548 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 1 ms 716 KB Output isn't correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Incorrect 173 ms 2328 KB Output isn't correct
14 Incorrect 103 ms 1484 KB Output isn't correct
15 Incorrect 18 ms 1568 KB Output isn't correct
16 Incorrect 122 ms 1100 KB Output isn't correct
17 Incorrect 450 ms 5432 KB Output isn't correct
18 Incorrect 53 ms 5196 KB Output isn't correct
19 Incorrect 123 ms 4940 KB Output isn't correct
20 Incorrect 124 ms 4492 KB Output isn't correct
21 Incorrect 303 ms 11812 KB Output isn't correct
22 Incorrect 177 ms 11464 KB Output isn't correct
23 Incorrect 931 ms 10096 KB Output isn't correct
24 Incorrect 111 ms 11528 KB Output isn't correct
25 Incorrect 284 ms 20424 KB Output isn't correct
26 Execution timed out 2065 ms 15696 KB Time limit exceeded
27 Execution timed out 2062 ms 23660 KB Time limit exceeded
28 Execution timed out 2076 ms 45248 KB Time limit exceeded
29 Execution timed out 2075 ms 45212 KB Time limit exceeded
30 Execution timed out 2073 ms 44872 KB Time limit exceeded
31 Execution timed out 2070 ms 14584 KB Time limit exceeded
32 Execution timed out 2085 ms 22136 KB Time limit exceeded