Submission #1005016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1005016	2024-06-22T06:12:58 Z	roadster	Tracks in the Snow (BOI13_tracks)	C++17	65.4167 / 100	485 ms	138844 KB

tracks

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;
using ll = long long;

#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define f first
#define s second
#define pb push_back

#define MOD 1e9 + 7
int h, w, ans = 1;
vector<string> snow(4000);
int dx[4] {1, -1, 0, 0}, dy[4] {0, 0, 1, -1};
vvi dist(4000, vi (4000));

bool isInside(int x, int y) {
    return x >= 0 && x < h && y >= 0 && y < h && snow[x][y] != '.';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> h >> w;
    for (int i = 0; i < h; i++) cin >> snow[i];
    
    deque<pi> dq;
    dq.push_front({0, 0});
    dist[0][0] = 1;
    
    while (!dq.empty()) {
        auto curr = dq.front();
        dq.pop_front();
        ans = max(ans, dist[curr.f][curr.s]);
        
        for (int i = 0; i < 4; i++) {
            int x = curr.f + dx[i], y = curr.s + dy[i];
            if (isInside(x, y) && dist[x][y] == 0) {
                if (snow[x][y] == snow[curr.f][curr.s]) {
                    dist[x][y] = dist[curr.f][curr.s];
                    dq.push_front({x, y});
                } else {
                    dist[x][y] = dist[curr.f][curr.s] + 1;
                    dq.push_back({x, y});
                }
            }
        }
    }
    
    cout << ans << "\n";
    return 0;
}

Subtask #1

21.6666666667 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	40 ms	63836 KB	Output isn't correct
2	Correct	33 ms	63312 KB	Output is correct
3	Correct	30 ms	63324 KB	Output is correct
4	Incorrect	35 ms	63828 KB	Output isn't correct
5	Correct	32 ms	63320 KB	Output is correct
6	Correct	30 ms	63320 KB	Output is correct
7	Correct	31 ms	63264 KB	Output is correct
8	Incorrect	32 ms	63324 KB	Output isn't correct
9	Correct	30 ms	63332 KB	Output is correct
10	Correct	33 ms	63312 KB	Output is correct
11	Correct	32 ms	63324 KB	Output is correct
12	Correct	32 ms	63316 KB	Output is correct
13	Correct	30 ms	63316 KB	Output is correct
14	Correct	33 ms	63324 KB	Output is correct
15	Correct	37 ms	63788 KB	Output is correct
16	Incorrect	39 ms	63832 KB	Output isn't correct
17	Correct	36 ms	63824 KB	Output is correct
18	Incorrect	36 ms	63628 KB	Output isn't correct

Subtask #2

43.75 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	311 ms	63452 KB	Output isn't correct
2	Correct	55 ms	66396 KB	Output is correct
3	Correct	148 ms	96600 KB	Output is correct
4	Incorrect	70 ms	70740 KB	Output isn't correct
5	Correct	96 ms	81948 KB	Output is correct
6	Correct	485 ms	94676 KB	Output is correct
7	Correct	411 ms	79868 KB	Output is correct
8	Incorrect	299 ms	63828 KB	Output isn't correct
9	Incorrect	28 ms	63320 KB	Output isn't correct
10	Incorrect	30 ms	63312 KB	Output isn't correct
11	Incorrect	286 ms	69208 KB	Output isn't correct
12	Correct	31 ms	63568 KB	Output is correct
13	Correct	51 ms	66464 KB	Output is correct
14	Incorrect	42 ms	65112 KB	Output isn't correct
15	Correct	38 ms	65356 KB	Output is correct
16	Incorrect	31 ms	64636 KB	Output isn't correct
17	Correct	88 ms	71376 KB	Output is correct
18	Correct	63 ms	71252 KB	Output is correct
19	Incorrect	73 ms	70740 KB	Output isn't correct
20	Incorrect	37 ms	70224 KB	Output isn't correct
21	Correct	99 ms	82516 KB	Output is correct
22	Correct	99 ms	82004 KB	Output is correct
23	Incorrect	127 ms	79320 KB	Output isn't correct
24	Correct	103 ms	82428 KB	Output is correct
25	Correct	166 ms	96592 KB	Output is correct
26	Correct	266 ms	138844 KB	Output is correct
27	Correct	330 ms	119448 KB	Output is correct
28	Correct	437 ms	110304 KB	Output is correct
29	Correct	440 ms	108740 KB	Output is correct
30	Correct	423 ms	113604 KB	Output is correct
31	Incorrect	324 ms	84820 KB	Output isn't correct
32	Correct	323 ms	111880 KB	Output is correct