Submission #773265

#	Time	Username	Problem	Language	Result	Execution time	Memory
773265		trnthienphc2003	Tracks in the Snow (BOI13_tracks)	C++17	19.79 / 100	940 ms	158736 KiB

tracks

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define fore(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define fort(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordt(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define forde(i, a, b) for (int i = (a), _b = (b); i > _b; --i)
#define trav(a, x) for (auto& a : x)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()

using namespace std;
using namespace __gnu_pbds;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef int64_t i64;
typedef pair<int,int> _ii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
constexpr int maxn=2e5+7;
constexpr i64 oo=1e9+7;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
char c[4007][4007];
int n, m, dp[4007][4007];

bool in(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m && c[x][y] != '*';
}

struct Node {
    int x, y, val;
    Node(int x, int y, int val): x(x), y(y), val(val) {}
};

void solve() {
   cin >> n >> m;

   deque <Node> dq;
   fort(i, 1, n) fort(j, 1, m) {
        dp[i][j] = oo;
        cin >> c[i][j];
   }

   dq.push_back({1, 1, 1});
   dp[1][1] = 1;

   while(dq.size()) {
        auto [x, y, val] = dq.front(); dq.pop_front();
        if(val > dp[x][y]) continue;
        fore(i, 0, 4) {
            int nX = x + dx[i], nY = y + dy[i];
            if(!in(nX, nY)) continue;

            int cost = (c[nX][nY] != c[x][y] ? 1 : 0);
            if(dp[nX][nY] > dp[x][y] + cost) {
                dp[nX][nY] = dp[x][y] + cost;
                if(cost) dq.push_back(Node(nX, nY, dp[nX][nY]));
                else dq.push_front(Node(nX, nY, dp[nX][nY]));

                // cout << x << " " << y <<  " : " << nX << " " << nY << " - " << cost << endl;
                // cout << dp[x][y] << " --- " << dp[nX][nY] << endl;
            }
        }
   }

    int ans = 0;
    fort(i, 1, n) fort(j, 1, m) {
        if(dp[i][j] < oo) maxi(ans, dp[i][j]);
    }
    cout << ans;
}

#define NAME "test."
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    if(fopen(NAME"inp", "r")) {
        freopen(NAME"inp", "r", stdin);
        freopen(NAME"out", "w", stdout);
    }

    int t=1;
    while(t--) solve();
}

Compilation message (stderr)

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

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