Submission #1098098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098098		The_Eureka	Tracks in the Snow (BOI13_tracks)	C++17	6.67 / 100	2118 ms	463812 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define alls(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define rep(i, n) for (int i = 1; i <= int(n); i++)
#define inc(i, l, r, d) for (int i = l; i <= r; i += d)
#define dec(i, r, l, d) for (int i = r; i >= l; i -= d) 
#define dbg(x) cerr << #x << " = " << x << endl;
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
const ld eps = 1e-12;
const ll inf = 1e16;
const ll mod = 998244353;
const ll mod1 = 1e9 + 87;
const ll mod2 = 127397154761;
ll qpow(ll a, ll b) {if (b == 0) return 1; ll ans = qpow(a, b >> 1); ans = ans * ans % mod; if (b & 1) ans = ans * a % mod; return ans;}
using namespace std;

void IOS(string name = "") {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    if ((int)name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}


const int maxn = 4005;

map<pii, vector<pair<pii, int>>> g;
int m, n;
char s[maxn][maxn];
int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
map<pii, int > dis;
map<pii, bool> vis;

bool check(int x1, int y1) {
    return x1 > 0 && y1 > 0 && x1 <= m && y1 <= n;
}

void bfs() {
    deque<pii> dq;
    rep(i, m) {
        rep(j, n) {
            dis[mk(i, j)] = INT_MAX - 10;
        }
    }
    dis[mk(1, 1)] = 1;
    dq.pb(mk(1, 1));
    vis[mk(1, 1)] = true;

    while (!dq.empty()) {
        pii u = dq.front(); dq.pop_front();

        for (auto it: g[u]) {
            pii v = it.first;
            int w = it.second;
            if (vis[v]) continue;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                vis[v] = true;
                if (w == 1) {
                    dq.pb(v);
                }
                else {
                    dq.push_front(v);
                }
            }
        }
    }
}

int main() {
    IOS();
    cin >> m >> n;
    rep(i, m) {
        rep(j, n) {
            cin >> s[i][j];
        }
    }
    rep(i, m) {
        rep(j, n) {
            forn(k, 4) {
                int x1 = i + d[k][0], y1 = j + d[k][1];
                if (check(x1, y1)) {
                    if (s[x1][y1] == s[i][j]) {
                        g[mk(i, j)].pb(mk(mk(x1, y1), 0));
                    }
                    else {
                        g[mk(i, j)].pb(mk(mk(x1, y1), 1));
                    }
                }
            }
        }
    }

    bfs();
    int ans = 0;
    rep(i, m) {
        rep(j, n) {
            if (s[i][j] != '.') {
                ans = max(ans, dis[mk(i, j)]);
            }
        }
    }
    cout << ans << endl;

    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void IOS(std::string)':
tracks.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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