Submission #484929

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484929	2021-11-05T18:14:39 Z	Olympia	Tracks in the Snow (BOI13_tracks)	C++17	82.5 / 100	2000 ms	57864 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() {
    //freopen("milkorder.in", "r", stdin);
    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	162 ms	1296 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	98 ms	1404 KB	Output is correct
5	Correct	11 ms	460 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	3 ms	332 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	13 ms	484 KB	Output is correct
11	Correct	23 ms	648 KB	Output is correct
12	Correct	55 ms	716 KB	Output is correct
13	Correct	9 ms	460 KB	Output is correct
14	Correct	11 ms	472 KB	Output is correct
15	Correct	118 ms	1100 KB	Output is correct
16	Correct	175 ms	1308 KB	Output is correct
17	Correct	55 ms	844 KB	Output is correct
18	Correct	95 ms	1424 KB	Output is correct

Subtask #2

52.5 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	716 KB	Output is correct
2	Correct	356 ms	3120 KB	Output is correct
3	Correct	1208 ms	33100 KB	Output is correct
4	Correct	282 ms	8184 KB	Output is correct
5	Correct	421 ms	13012 KB	Output is correct
6	Execution timed out	2086 ms	57864 KB	Time limit exceeded
7	Correct	4 ms	716 KB	Output is correct
8	Correct	4 ms	788 KB	Output is correct
9	Correct	14 ms	608 KB	Output is correct
10	Correct	3 ms	332 KB	Output is correct
11	Correct	3 ms	716 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	397 ms	3120 KB	Output is correct
14	Correct	213 ms	2344 KB	Output is correct
15	Correct	41 ms	2416 KB	Output is correct
16	Correct	192 ms	1320 KB	Output is correct
17	Correct	870 ms	8808 KB	Output is correct
18	Correct	174 ms	8588 KB	Output is correct
19	Correct	283 ms	8184 KB	Output is correct
20	Correct	345 ms	7492 KB	Output is correct
21	Correct	733 ms	13540 KB	Output is correct
22	Correct	440 ms	13052 KB	Output is correct
23	Correct	1820 ms	11332 KB	Output is correct
24	Correct	390 ms	13592 KB	Output is correct
25	Correct	753 ms	33044 KB	Output is correct
26	Execution timed out	2089 ms	15688 KB	Time limit exceeded
27	Execution timed out	2061 ms	34776 KB	Time limit exceeded
28	Execution timed out	2060 ms	57800 KB	Time limit exceeded
29	Execution timed out	2086 ms	57828 KB	Time limit exceeded
30	Execution timed out	2073 ms	57240 KB	Time limit exceeded
31	Execution timed out	2081 ms	17276 KB	Time limit exceeded
32	Execution timed out	2088 ms	34008 KB	Time limit exceeded