Submission #715015

#	Time	Username	Problem	Language	Result	Execution time	Memory
715015		mariacichosz	Tracks in the Snow (BOI13_tracks)	C++17	29.58 / 100	2097 ms	307596 KiB

tracks

#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({0, {nx, ny}});
            }
            if (tab[nx][ny] != tab[sx][sy]){
                dis[nx][ny] = min(dis[sx][sy] + 1, dis[nx][ny]);
                q.push({-1, {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: 3.3333333333333335 / 30
• Subtask 2: 26.25 / 70