Submission #500383

#	Time	Username	Problem	Language	Result	Execution time	Memory
500383		joshualiu555	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	601 ms	138756 KiB

tracks

/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, x, n) for (int i = x; i < n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define sz size
#define pof pop_front
#define pob pop_back
#define pf push_front
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))

using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};

/*
 *
*/

//

void solve() {

}

int n, m;
char a[4001][4001];

int dist[4001][4001];
deque<pair<int, int>> q;

bool valid(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m && a[x][y] != '.';
}

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

//    ifstream cin(".in");
//    ofstream cout(".out");

//    int t;
//    cin >> t;
//    while (t--) {
//        solve();
//    }

    FOR(i, 0, 4001) {
        FOR(j, 0, 4001) {
            dist[i][j] = 1e9;
        }
    }

    cin >> n >> m;
    FOR(i, 0, n) cin >> a[i];

    dist[0][0] = 0;
    q.pf(mp(0, 0));
    while (q.sz()) {
        int x = q.front().first, y = q.front().second;
        q.pof();
        FOR(i, 0, 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!valid(nx, ny)) continue;
            int w = (a[x][y] == a[nx][ny]) ^ 1;
            if (dist[x][y] + w < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 1) q.pb(mp(nx, ny));
                else q.pf(mp(nx, ny));
            }
        }
    }
    
//    FOR(i, 0, n) {
//        FOR(j, 0, m) {
//            cerr << dist[i][j] << ' ';
//        }
//        cerr << '\n';
//    }

    int ans = 0;
    FOR(i, 0, n) {
        FOR(j, 0, m) {
            if (dist[i][j] == 1e9) continue;
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans + 1 << '\n';

    return 0;
}

/*
 *
*/

//5 8
//FFR.....
//.FRRR...
//.FFFFF..
//..RRRFFR
//.....FFF

Compilation message (stderr)

tracks.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
   12 | #pragma gcc target ("avx2")
      | 
tracks.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   13 | #pragma gcc optimization ("O3")
      | 
tracks.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   14 | #pragma gcc optimization ("unroll-loops")
      |

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