oj.uz

Submission #769506

# Submission time Handle Problem Language Result Execution time Memory
769506 2023-06-29T16:46:13 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
75.9375 / 100
 2000 ms 201524 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i = (a); i < (b); i++)
typedef long long ll;

int H, W;
vector<string> grid;

vector<vector<ll>> visited; // bitset ?

priority_queue<vector<ll>> q;

void dfs(int hat, int wat, ll num)
{
    if (visited[hat][wat]>0) return;
    if (grid[hat][wat] == '.') return;
    visited[hat][wat] = num;

    char ch = grid[hat][wat];
    if (hat + 1 < H) {
        if (grid[hat + 1][wat] == ch) q.push({-num, hat + 1, wat});
        else q.push({-(num + 1), hat + 1, wat});
    }
    if (wat + 1 < W) {
        if (grid[hat][wat + 1] == ch) q.push({-num, hat, wat + 1});
        else q.push({-(num + 1), hat, wat + 1});
    }
    if (hat - 1 >= 0) {
        if (grid[hat - 1][wat] == ch) q.push({-num, hat - 1, wat});
        else q.push({-(num + 1), hat - 1, wat});
    }
    if (wat - 1 >= 0) {
        if (grid[hat][wat - 1] == ch) q.push({-num, hat, wat - 1});
        else q.push({-(num + 1), hat, wat - 1});
    }
}

int32_t main()
{
    cin>>H>>W;
    grid.assign(H, "");
    rep(i,0,H){
        cin>>grid[i];
    }

    visited.assign(H, vector<ll>(W, -1));
    q.push({-1,0,0});
    while(!q.empty())
    {
        vector<ll> x = q.top();
        q.pop();
        dfs(x[1], x[2], -(x[0]));
    }

    ll ans = 1;
    rep(i,0,H){
        rep(j,0,W){
            ans = max(ans, visited[i][j]);
        }
    }
    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 4180 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 148 ms 4268 KB Output is correct
5 Correct 19 ms 1108 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 24 ms 1040 KB Output is correct
11 Correct 35 ms 1284 KB Output is correct
12 Correct 87 ms 1864 KB Output is correct
13 Correct 19 ms 1108 KB Output is correct
14 Correct 23 ms 1216 KB Output is correct
15 Correct 187 ms 3352 KB Output is correct
16 Correct 265 ms 4188 KB Output is correct
17 Correct 106 ms 3048 KB Output is correct
18 Correct 150 ms 4284 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1236 KB Output is correct
2 Correct 689 ms 15548 KB Output is correct
3 Execution timed out 2082 ms 157212 KB Time limit exceeded
4 Correct 637 ms 37484 KB Output is correct
5 Correct 1425 ms 83084 KB Output is correct
6 Execution timed out 2083 ms 201524 KB Time limit exceeded
7 Correct 8 ms 1236 KB Output is correct
8 Correct 8 ms 1236 KB Output is correct
9 Correct 26 ms 1552 KB Output is correct
10 Correct 5 ms 980 KB Output is correct
11 Correct 6 ms 1364 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 676 ms 15528 KB Output is correct
14 Correct 384 ms 9436 KB Output is correct
15 Correct 114 ms 10316 KB Output is correct
16 Correct 337 ms 6740 KB Output is correct
17 Correct 1805 ms 40512 KB Output is correct
18 Correct 460 ms 39660 KB Output is correct
19 Correct 652 ms 37512 KB Output is correct
20 Correct 604 ms 34348 KB Output is correct
21 Correct 1555 ms 85720 KB Output is correct
22 Correct 1431 ms 82896 KB Output is correct
23 Execution timed out 2085 ms 71760 KB Time limit exceeded
24 Correct 1221 ms 84104 KB Output is correct
25 Execution timed out 2048 ms 156780 KB Time limit exceeded
26 Execution timed out 2067 ms 110392 KB Time limit exceeded
27 Execution timed out 2079 ms 158596 KB Time limit exceeded
28 Execution timed out 2080 ms 200736 KB Time limit exceeded
29 Execution timed out 2072 ms 198216 KB Time limit exceeded
30 Execution timed out 2082 ms 197092 KB Time limit exceeded
31 Execution timed out 2072 ms 103568 KB Time limit exceeded
32 Execution timed out 2092 ms 157152 KB Time limit exceeded