oj.uz

Submission #715016

# Submission time Handle Problem Language Result Execution time Memory
715016 2023-03-25T20:13:53 Z mariacichosz Tracks in the Snow (BOI13_tracks) C++17
39.5833 / 100
 2000 ms 291956 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define sz size
#define st first
#define nd second

const int N = 4010;
const int inf = 1e9 + 3;

int h, w;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int dis[N][N];
bool vis[N][N];
char tab[N][N];

int ans;

void bfs(int x = 1, int y = 1){
    priority_queue<pair<int, pii>> q;
    vis[x][y] = 1;
    dis[x][y] = 1;
    q.push({1, {x, y}});
    while (!q.empty()){
        auto v = q.top();
        q.pop();
        int sx = v.nd.st, sy = v.nd.nd;
        ans = max(dis[sx][sy], ans);
        vis[sx][sy] = 1;
        for (int i = 0; i < 4; i ++){
            int nx = sx + dx[i], ny = sy + dy[i];
            if (nx < 1 || ny < 1 || nx > h || ny > w) continue;
            if (vis[nx][ny]) continue;
            if (tab[nx][ny] == '.') continue;
            if (tab[nx][ny] == tab[sx][sy]){
                dis[nx][ny] = min(dis[sx][sy], dis[nx][ny]);
                q.push({-1 * dis[nx][ny], {nx, ny}});
            }
            if (tab[nx][ny] != tab[sx][sy]){
                dis[nx][ny] = min(dis[sx][sy] + 1, dis[nx][ny]);
                q.push({-1 * dis[nx][ny], {nx, ny}});
            }
        }
    }
}

void cl(){
    for (int i = 0; i < N; i ++){
        for (int j = 0; j < N; j ++){
            dis[i][j] = inf;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cl();
    
    cin >> h >> w;
    for (int i = 1; i <= h; i ++){
        for (int j = 1; j <= w; j ++){
            cin >> tab[i][j];
        }
    }
    bfs();
    cout << ans << "\n";
}

Subtask #1
13.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 264384 KB Time limit exceeded
2 Correct 28 ms 63384 KB Output is correct
3 Correct 38 ms 63732 KB Output is correct
4 Execution timed out 2095 ms 263548 KB Time limit exceeded
5 Correct 150 ms 67100 KB Output is correct
6 Correct 29 ms 63372 KB Output is correct
7 Correct 40 ms 63704 KB Output is correct
8 Execution timed out 2074 ms 260868 KB Time limit exceeded
9 Correct 29 ms 64052 KB Output is correct
10 Execution timed out 2061 ms 114644 KB Time limit exceeded
11 Execution timed out 2076 ms 261996 KB Time limit exceeded
12 Execution timed out 2084 ms 164188 KB Time limit exceeded
13 Correct 148 ms 67132 KB Output is correct
14 Correct 159 ms 67100 KB Output is correct
15 Execution timed out 2082 ms 264340 KB Time limit exceeded
16 Execution timed out 2064 ms 264312 KB Time limit exceeded
17 Execution timed out 2066 ms 165720 KB Time limit exceeded
18 Execution timed out 2080 ms 263404 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 93128 KB Output is correct
2 Execution timed out 2079 ms 122544 KB Time limit exceeded
3 Execution timed out 2063 ms 143992 KB Time limit exceeded
4 Execution timed out 2070 ms 102760 KB Time limit exceeded
5 Correct 264 ms 86728 KB Output is correct
6 Execution timed out 2070 ms 277104 KB Time limit exceeded
7 Correct 50 ms 94528 KB Output is correct
8 Correct 50 ms 93140 KB Output is correct
9 Execution timed out 2079 ms 112816 KB Time limit exceeded
10 Correct 35 ms 63272 KB Output is correct
11 Correct 48 ms 94012 KB Output is correct
12 Correct 39 ms 64324 KB Output is correct
13 Execution timed out 2090 ms 122552 KB Time limit exceeded
14 Execution timed out 2074 ms 119736 KB Time limit exceeded
15 Correct 60 ms 71116 KB Output is correct
16 Execution timed out 2084 ms 165088 KB Time limit exceeded
17 Execution timed out 2081 ms 177764 KB Time limit exceeded
18 Correct 145 ms 78952 KB Output is correct
19 Execution timed out 2090 ms 102832 KB Time limit exceeded
20 Execution timed out 2074 ms 126544 KB Time limit exceeded
21 Execution timed out 2082 ms 100128 KB Time limit exceeded
22 Correct 257 ms 86688 KB Output is correct
23 Execution timed out 2095 ms 132236 KB Time limit exceeded
24 Correct 232 ms 87664 KB Output is correct
25 Correct 586 ms 94672 KB Output is correct
26 Execution timed out 2091 ms 287976 KB Time limit exceeded
27 Execution timed out 2088 ms 291956 KB Time limit exceeded
28 Execution timed out 2087 ms 277152 KB Time limit exceeded
29 Execution timed out 2079 ms 278744 KB Time limit exceeded
30 Execution timed out 2089 ms 277692 KB Time limit exceeded
31 Execution timed out 2077 ms 285516 KB Time limit exceeded
32 Execution timed out 2094 ms 291856 KB Time limit exceeded