Submission #445070

#	Time	Username	Problem	Language	Result	Execution time	Memory
445070		KazamaHoang	Tracks in the Snow (BOI13_tracks)	C++17	83.02 / 100	898 ms	121664 KiB

tracks

#include <bits/stdc++.h>
#define F first
#define S second
#define eb emplace_back
#define bit(x, i) (((x) >> (i)) & 1)
#define sz(x) ((int)x.size())

using namespace std;
using ll = long long;

const int inf = 1061109567;
const ll INF = 4557430888798830399;
const int MOD = 1e9 + 7;
const int dx[] = {0, 1, -1, 0};
const int dy[] = {1, 0, 0, -1};

int numRow, numCol;
char snow[4005][4005];
int dist[4005][4005];

bool outSide(int ux, int vy) {
    if (ux == 0 || ux == numRow || vy == 0 || vy == numCol || snow[ux][vy] == '.')
        return true;
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    #define Task ""
    if (fopen(Task".in", "r")) {
        freopen(Task".in", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> numRow >> numCol;
    for (int i = 1; i <= numRow; ++ i)
        for (int j = 1; j <= numCol; ++ j)
            cin >> snow[i][j];
    deque <pair <int, int>> dq;
    dq.push_back({1, 1});
    dist[1][1] = 1;
    int res = 0;
    while (!dq.empty()) {
        int u = dq.front().F;
        int v = dq.front().S;
        dq.pop_front();
        res = max(res, dist[u][v]);
        for (int i = 0; i <= 3; ++ i) {
            int ux = u + dx[i];
            int vy = v + dy[i];
            if (outSide(ux, vy) || dist[ux][vy] != 0)
                continue;
            if (snow[ux][vy] == snow[u][v]) {
                dq.push_front({ux, vy});
                dist[ux][vy] = dist[u][v];
            } else {
                dq.push_back({ux, vy});
                dist[ux][vy] = dist[u][v] + 1;
            }
        }
    }
    cout << res;
    return 0;
}

// Written by Kazama Hoang ^^

Compilation message (stderr)

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

• Subtask 1: 28.333333333333332 / 30
• Subtask 2: 54.6875 / 70