oj.uz

Submission #769507

# Submission time Handle Problem Language Result Execution time Memory
769507 2023-06-29T16:51:00 Z Ellinor Tracks in the Snow (BOI13_tracks) C++14
39.5833 / 100
 2000 ms 484352 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)
{
    visited[hat][wat] = num;

    char ch = grid[hat][wat];
    if (hat + 1 < H) {
        if (visited[hat + 1][wat] == -1 && grid[hat + 1][wat] != '.') {
            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 (visited[hat][wat + 1] == -1 && grid[hat][wat + 1] != '.') {
            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 (visited[hat - 1][wat] == -1 && grid[hat - 1][wat] != '.') {
            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 (visited[hat][wat - 1] == -1 && grid[hat][wat - 1] != '.') {
            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
13.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2096 ms 330952 KB Time limit exceeded
2 Correct 1 ms 212 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Execution timed out 2089 ms 330016 KB Time limit exceeded
5 Correct 189 ms 6248 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 7 ms 504 KB Output is correct
8 Execution timed out 2112 ms 328560 KB Time limit exceeded
9 Correct 1 ms 340 KB Output is correct
10 Execution timed out 2094 ms 165108 KB Time limit exceeded
11 Execution timed out 2091 ms 328888 KB Time limit exceeded
12 Execution timed out 2097 ms 218572 KB Time limit exceeded
13 Correct 188 ms 6196 KB Output is correct
14 Correct 187 ms 6200 KB Output is correct
15 Execution timed out 2063 ms 331060 KB Time limit exceeded
16 Execution timed out 2080 ms 330900 KB Time limit exceeded
17 Execution timed out 2088 ms 181796 KB Time limit exceeded
18 Execution timed out 2098 ms 330020 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 852 KB Output is correct
2 Execution timed out 2086 ms 113776 KB Time limit exceeded
3 Execution timed out 2094 ms 238004 KB Time limit exceeded
4 Execution timed out 2097 ms 125500 KB Time limit exceeded
5 Correct 333 ms 82220 KB Output is correct
6 Execution timed out 2105 ms 382464 KB Time limit exceeded
7 Correct 2 ms 852 KB Output is correct
8 Correct 3 ms 852 KB Output is correct
9 Execution timed out 2077 ms 164992 KB Time limit exceeded
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 852 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Execution timed out 2079 ms 113804 KB Time limit exceeded
14 Execution timed out 2080 ms 91128 KB Time limit exceeded
15 Correct 32 ms 9940 KB Output is correct
16 Execution timed out 2089 ms 105084 KB Time limit exceeded
17 Execution timed out 2075 ms 203948 KB Time limit exceeded
18 Correct 142 ms 39240 KB Output is correct
19 Execution timed out 2041 ms 125572 KB Time limit exceeded
20 Execution timed out 2072 ms 119948 KB Time limit exceeded
21 Execution timed out 2041 ms 126156 KB Time limit exceeded
22 Correct 359 ms 82280 KB Output is correct
23 Execution timed out 2082 ms 172320 KB Time limit exceeded
24 Correct 309 ms 83448 KB Output is correct
25 Correct 741 ms 155844 KB Output is correct
26 Execution timed out 2088 ms 437960 KB Time limit exceeded
27 Execution timed out 2091 ms 484352 KB Time limit exceeded
28 Execution timed out 2073 ms 373116 KB Time limit exceeded
29 Execution timed out 2073 ms 484156 KB Time limit exceeded
30 Execution timed out 2109 ms 480916 KB Time limit exceeded
31 Execution timed out 2091 ms 451868 KB Time limit exceeded
32 Execution timed out 2090 ms 484288 KB Time limit exceeded