oj.uz

Submission #484936

# Submission time Handle Problem Language Result Execution time Memory
484936 2021-11-05T18:26:38 Z Olympia Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 50 ms 20420 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;
            pair<int,int> nxt = {p.first + dx, p.second + dy};
            if (nxt.first >= 0 && nxt.second >= 0 && nxt.first < n && nxt.second < m
                && grid[nxt.first][nxt.second] != '.') {
                if (hasVisited[nxt.first][nxt.second]) {
                    myMax = max(myMax, dist + (grid[nxt.first][nxt.second] != grid[loc.first][loc.second]));
                    continue;
                }
                q.push(make_pair(-dist - (grid[nxt.first][nxt.second] != grid[loc.first][loc.second]),
                                 make_pair(loc.first + dx, loc.second + dy)));
            }
        }
    }
    cout << myMax;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 628 KB Output isn't correct
2 Incorrect 0 ms 204 KB Output isn't correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Incorrect 1 ms 460 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 0 ms 204 KB Output isn't correct
7 Incorrect 0 ms 204 KB Output isn't correct
8 Incorrect 0 ms 204 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 1 ms 332 KB Output isn't correct
11 Incorrect 0 ms 332 KB Output isn't correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Incorrect 1 ms 332 KB Output isn't correct
14 Incorrect 1 ms 332 KB Output isn't correct
15 Incorrect 2 ms 588 KB Output isn't correct
16 Incorrect 1 ms 588 KB Output isn't correct
17 Incorrect 1 ms 540 KB Output isn't correct
18 Incorrect 1 ms 460 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 5 ms 2252 KB Output isn't correct
3 Incorrect 50 ms 20384 KB Output isn't correct
4 Incorrect 13 ms 4916 KB Output isn't correct
5 Incorrect 25 ms 11340 KB Output isn't correct
6 Incorrect 46 ms 20296 KB Output isn't correct
7 Incorrect 1 ms 716 KB Output isn't correct
8 Incorrect 1 ms 588 KB Output isn't correct
9 Incorrect 1 ms 332 KB Output isn't correct
10 Incorrect 0 ms 332 KB Output isn't correct
11 Incorrect 1 ms 716 KB Output isn't correct
12 Incorrect 0 ms 332 KB Output isn't correct
13 Incorrect 7 ms 2252 KB Output isn't correct
14 Incorrect 4 ms 1428 KB Output isn't correct
15 Incorrect 3 ms 1468 KB Output isn't correct
16 Incorrect 2 ms 1100 KB Output isn't correct
17 Incorrect 13 ms 5196 KB Output isn't correct
18 Incorrect 12 ms 5220 KB Output isn't correct
19 Incorrect 11 ms 4868 KB Output isn't correct
20 Incorrect 10 ms 4448 KB Output isn't correct
21 Incorrect 29 ms 11708 KB Output isn't correct
22 Incorrect 27 ms 11376 KB Output isn't correct
23 Incorrect 22 ms 9796 KB Output isn't correct
24 Incorrect 31 ms 11468 KB Output isn't correct
25 Incorrect 47 ms 20340 KB Output isn't correct
26 Incorrect 35 ms 15536 KB Output isn't correct
27 Incorrect 45 ms 20420 KB Output isn't correct
28 Incorrect 46 ms 20308 KB Output isn't correct
29 Incorrect 49 ms 20380 KB Output isn't correct
30 Incorrect 47 ms 20036 KB Output isn't correct
31 Incorrect 30 ms 12968 KB Output isn't correct
32 Incorrect 46 ms 20380 KB Output isn't correct