oj.uz

Submission #769502

# Submission time Handle Problem Language Result Execution time Memory
769502 2023-06-29T16:38:19 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
75.9375 / 100
 2000 ms 217932 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<bool>> visited; // bitset ?
vector<vector<ll>> dp;

priority_queue<vector<ll>> q;

void dfs(int hat, int wat, ll num)
{
    //cerr << hat << " " << wat << " " << num << "\n";

    if (visited[hat][wat]) return;
    if (grid[hat][wat] == '.') return;
    visited[hat][wat] = true;

    dp[hat][wat] = num;

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

    if (hat + 1 < H) if (grid[hat + 1][wat] != ch) q.push({-(num + 1), hat + 1, wat});
    if (wat + 1 < W) if (grid[hat][wat + 1] != ch) q.push({-(num + 1), hat, wat + 1});
    if (hat - 1 >= 0) if (grid[hat - 1][wat] != ch) q.push({-(num + 1), hat - 1, wat});
    if (wat - 1 >= 0) if (grid[hat][wat - 1] != ch) 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<bool>(W, false));
    dp.assign(H, vector<ll>(W, 0));
    q.push({-1,0,0});
    while(!q.empty())
    {
        auto 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, dp[i][j]);
            //cerr << dp[i][j]<< " ";
        }
        //cerr << "\n";
    }

    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 4356 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 288 KB Output is correct
4 Correct 167 ms 4616 KB Output is correct
5 Correct 19 ms 1236 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 5 ms 432 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 24 ms 1108 KB Output is correct
11 Correct 36 ms 1336 KB Output is correct
12 Correct 89 ms 2032 KB Output is correct
13 Correct 19 ms 1320 KB Output is correct
14 Correct 24 ms 1316 KB Output is correct
15 Correct 195 ms 3680 KB Output is correct
16 Correct 286 ms 4480 KB Output is correct
17 Correct 109 ms 3280 KB Output is correct
18 Correct 164 ms 4484 KB Output is correct

Subtask #2
45.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1620 KB Output is correct
2 Correct 698 ms 17320 KB Output is correct
3 Execution timed out 2079 ms 174928 KB Time limit exceeded
4 Correct 651 ms 41708 KB Output is correct
5 Correct 1313 ms 92908 KB Output is correct
6 Execution timed out 2061 ms 217824 KB Time limit exceeded
7 Correct 8 ms 1620 KB Output is correct
8 Correct 8 ms 1664 KB Output is correct
9 Correct 28 ms 1552 KB Output is correct
10 Correct 5 ms 980 KB Output is correct
11 Correct 6 ms 1620 KB Output is correct
12 Correct 5 ms 564 KB Output is correct
13 Correct 673 ms 17380 KB Output is correct
14 Correct 389 ms 10532 KB Output is correct
15 Correct 113 ms 11424 KB Output is correct
16 Correct 350 ms 7392 KB Output is correct
17 Correct 1834 ms 45060 KB Output is correct
18 Correct 451 ms 44268 KB Output is correct
19 Correct 655 ms 41696 KB Output is correct
20 Correct 610 ms 38220 KB Output is correct
21 Correct 1562 ms 96076 KB Output is correct
22 Correct 1327 ms 92940 KB Output is correct
23 Execution timed out 2068 ms 80408 KB Time limit exceeded
24 Correct 1158 ms 94240 KB Output is correct
25 Execution timed out 2043 ms 174600 KB Time limit exceeded
26 Execution timed out 2082 ms 123916 KB Time limit exceeded
27 Execution timed out 2084 ms 176272 KB Time limit exceeded
28 Execution timed out 2082 ms 217932 KB Time limit exceeded
29 Execution timed out 2088 ms 216328 KB Time limit exceeded
30 Execution timed out 2089 ms 215776 KB Time limit exceeded
31 Execution timed out 2088 ms 114952 KB Time limit exceeded
32 Execution timed out 2083 ms 174984 KB Time limit exceeded