Submission #727909

#	Time	Username	Problem	Language	Result	Execution time	Memory
727909		ace_in_the_hole	Tracks in the Snow (BOI13_tracks)	C++17	19.79 / 100	806 ms	137028 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
//https://oj.uz/problem/view/BOI13_tracks
typedef long long Int;

const int N = 4005;
char board[N][N];
int dist[N][N];
using Cell = pair<int,int>;
#define x first
#define y second

#define all(v) (v).begin(), (v).end()
#define cst(T) const T&

template<class A, class B> bool umin(A& var, cst(B) val) {
    return (val < var) ? (var = val, true) : false;
}
template<class A, class B> bool umax(A& var, cst(B) val) {
    return (var < val) ? (var = val, true) : false;
}

const int INF = 1e9;
const int dx[] {-1,+1, 0, 0};
const int dy[] { 0, 0,-1,+1};

void solve() 
{
    int hei, wid;
    cin >> hei >> wid;
    for (int i = 1; i <= hei; i++)
        for (int j = 1; j <= wid; j++) {
            dist[i][j] = INF;
            cin >> board[i][j];
        }
    deque<Cell> bfs;
    bfs.push_front(Cell(1,1));
    dist[1][1] = 1;
    int ans = 0;
    while (!bfs.empty()) {
        auto u = bfs.front(); bfs.pop_front();
        umax(ans, dist[u.x][u.y]);
        for (int d = 0; d < 4; d++) {
            Cell v(u.x + dx[d], u.y + dy[d]);
            if (min(v.x,v.x) < 1 or v.x > hei or v.y > wid) continue;
            int edge = (board[v.x][v.y] != board[u.x][u.y]);
            if (umin(dist[v.x][v.y], dist[u.x][u.y] + edge))
                edge ? bfs.push_back(v) : bfs.push_front(v);
        }
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define task "WF"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6.666666666666667 / 30
• Subtask 2: 13.125 / 70