Submission #1272762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272762		neel	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	976 ms	256752 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

// ---------- debug utilities ----------
#ifndef Local
    #define debug(...)
    #define debugArr(...)
#else
    #include <debug.cpp>
    auto start = chrono::high_resolution_clock::now();
#endif


// ---------- shortcut macros ----------
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define len(x) (int)(x).size()
#define pb push_back
#define print1(zzz) for(auto zzzz: zzz) cout << zzzz << ' ';cout<<endl;
#define print2(zzz) for (auto &zzzzz : zzz) {print1(zzzzz)}
#define space cout << endl;
#define sum(v) (accumulate((v).begin(), (v).end(), 0LL))
#define lb(v, x) (lower_bound((v).begin(), (v).end(), (x)) - (v).begin())  
#define ub(v, x) (upper_bound((v).begin(), (v).end(), (x)) - (v).begin())  
#define execute ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

// ----------- constants -----------
#define PI 3.14159265358979323846
#define INF 1e18
#define MOD 1000000007
#define MOD2 998244353

// ---------- type aliases ----------
#define ll long long
#define int long long
#define vi vector<int> 
#define vc vector<char> 
#define vs vector<string> 
#define vvc vector<vector<char>> 
#define vvi vector<vector<int>> 
#define pii pair<int, int> 

// ---------- input macros ----------
#define msb(x) (x == 0 ? -1 : 1ll<<(63 - __builtin_clzll(x)))      
#define lsb(x) (x == 0 ? -1 : 1ll<<(__builtin_ctzll(x)))   
#define pc(x) (__builtin_popcountll(x))
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}

int h, w;
vvc med;

void solve() {
    cin >> h >> w;
    med.assign(h, vector<char>(w));
    vector<vector<int>> vis(h, vector<int>(w, 1e9));
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            cin >> med[i][j];
        }
    }

    deque<array<int,3>> qu;
    qu.push_back({0,0,0});
    vis[0][0] = 0;

    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};

    while (!qu.empty()) {
        auto [x,y,c] = qu.front();
        qu.pop_front();

        for (int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if (nx<0 || nx>=h || ny<0 || ny>=w) continue;
            if (med[nx][ny]=='.') continue;

            int nc = c + (med[x][y] != med[nx][ny]);

            if (vis[nx][ny] > nc) {
                vis[nx][ny] = nc;
                if (med[x][y] == med[nx][ny])
                    qu.push_front({nx,ny,nc});
                else
                    qu.push_back({nx,ny,nc});
            }
        }
    }

    int ans = 0; 

    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            if (med[i][j] == '.') continue;
            ans = max(ans, vis[i][j]);
        }
    }


    cout << ans+1;
}

int32_t main(){
    // cout << fixed << setprecision(10);
    #ifdef Local
        // freopen("input.txt", "r+", stdin);
        // freopen("output.txt", "w+", stdout);
    #endif

    execute
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    
    #ifdef Local
        chrono::duration<double> elapsed = chrono::high_resolution_clock::now() - start;
        cerr << fixed << setprecision(6) << "\nTime: " << elapsed.count() << "s\n"; 
    #endif
    return 0;
}

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