Submission #484930

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484930	2021-11-05T18:15:33 Z	Olympia	Tracks in the Snow (BOI13_tracks)	C++17	82.5 / 100	2000 ms	45308 KB

tracks

#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] != '.') {
                    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

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	1164 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	91 ms	1380 KB	Output is correct
5	Correct	8 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	3 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	11 ms	448 KB	Output is correct
11	Correct	23 ms	588 KB	Output is correct
12	Correct	55 ms	740 KB	Output is correct
13	Correct	8 ms	332 KB	Output is correct
14	Correct	8 ms	456 KB	Output is correct
15	Correct	108 ms	844 KB	Output is correct
16	Correct	160 ms	1164 KB	Output is correct
17	Correct	54 ms	772 KB	Output is correct
18	Correct	91 ms	1400 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	716 KB	Output is correct
2	Correct	316 ms	2380 KB	Output is correct
3	Correct	928 ms	20676 KB	Output is correct
4	Correct	210 ms	5068 KB	Output is correct
5	Correct	254 ms	11640 KB	Output is correct
6	Execution timed out	2085 ms	45216 KB	Time limit exceeded
7	Correct	2 ms	716 KB	Output is correct
8	Correct	2 ms	716 KB	Output is correct
9	Correct	14 ms	576 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	2 ms	716 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	318 ms	2500 KB	Output is correct
14	Correct	180 ms	1612 KB	Output is correct
15	Correct	22 ms	1612 KB	Output is correct
16	Correct	177 ms	1256 KB	Output is correct
17	Correct	805 ms	5580 KB	Output is correct
18	Correct	90 ms	5196 KB	Output is correct
19	Correct	210 ms	5068 KB	Output is correct
20	Correct	235 ms	4616 KB	Output is correct
21	Correct	570 ms	12100 KB	Output is correct
22	Correct	252 ms	11600 KB	Output is correct
23	Correct	1613 ms	10228 KB	Output is correct
24	Correct	214 ms	11680 KB	Output is correct
25	Correct	435 ms	20668 KB	Output is correct
26	Execution timed out	2075 ms	15896 KB	Time limit exceeded
27	Execution timed out	2081 ms	22264 KB	Time limit exceeded
28	Execution timed out	2085 ms	45308 KB	Time limit exceeded
29	Execution timed out	2089 ms	45184 KB	Time limit exceeded
30	Execution timed out	2033 ms	44956 KB	Time limit exceeded
31	Execution timed out	2082 ms	16172 KB	Time limit exceeded
32	Execution timed out	2083 ms	22208 KB	Time limit exceeded