Submission #1125866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125866		jcoves	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	611 ms	110852 KiB

tracks

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

#ifdef LOCAL_RUN
    #include "debug_common.h"
    #else
    #define trace(...) ;
    #define dbg(...) ;
    #define dbgc(...) ;
    #define debug(x) ;
    #define debuga(a, n) ;
    #define debug2(x, y) ;
    #define debug3(x, y, z) ;
    #define debug4(x, y, z, w) ;
    #define debug5(a,b,c,d,e) ;
    #define lassert(x) ;
    #define dassert(x, ...) ;
    int recur_depth = 0; bool rec_indent = true;
    const bool isLocal = false;
    #endif

    #define pb push_back
    #define eb emplace_back
    #define popb pop_back
    #define all(v) begin(v), end(v)
    #define rall(v) (v).rbegin(),(v).rend()
    #define make_unique(v) (v).erase(unique(all(v)), (v).end())
    #define sz(c) ((int) c.size())
    #define forn(i,n) for(auto i=(n)-(n);i<(n);i++)
    #define fornn(i,s,n) for(auto i=(n)-(n)+(s);i<(n);i++)
    #define forb(i,n) for(auto i=(n)-1;i>=0;i--)
    #define forbn(i,s,n) for(auto i=(n)-1;i>=(s);i--)
    #define forbit(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
    #define mem(a,b) memset(a,b,sizeof(a))
    #define abs(x) (((x) < 0) ? -(x) : (x))
    #define sqr(x) ((x) * (x))
    #define sqrt(x) sqrt(abs(x))
    #define has(c,x) (c.find(x) != c.end())
    #define pw(x) (1LL << (x))
    #define ibit(x,i) (((x) >> (i)) & 1)
    #define preturn(...) {out(__VA_ARGS__); return;}
    #define data(v) v.data(), sz(v) // vi -> vai
    #define gtime() ((double(clock()) - 0)/CLOCKS_PER_SEC)

    typedef stringstream sstr;
    typedef long long ll;
    typedef pair<int, int> pii;
    typedef pair<ll,ll> pll;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<pii> vpii;
    typedef vector<vi> vvi;
    typedef vector<vll> vvll;
    typedef valarray<int> vai;
    template <class T>
    using min_pq = priority_queue<T, vector<T>, greater<T>>;
    template <class T>
    using vc = vector<T>;
    template <class T>
    using vvc = vector<vc<T>>;
    template <class T>
    using vvvc = vector<vvc<T>>;
    template <class T>
    using vvvvc = vector<vvvc<T>>;
    template <class T>
    using vvvvvc = vector<vvvvc<T>>;

    template<class F>
    struct y_comb{
        F f;
        template<class T> explicit y_comb(T &&f_in): f(forward<T>(f_in)){ }
        template<class ...Args> decltype(auto) operator()(Args &&...args){ return f(ref(*this), forward<Args>(args)...); }
    };
    template<class F>
    decltype(auto) yf(F &&f){
        return y_comb<decay_t<F>>(forward<F>(f));
    }

    inline int ni(){ int x; cin >> x;   return x; }
    inline ll  nl() { ll  x; cin >> x; return x; }

    template <class T> void mmin(T& a, const T& b) {
        a = (a) < (b) ? (a) : (b);
    }
    template <class T> void mmax(T& a, const T& b) {
        a = (a) > (b) ? (a) : (b);
    }
    template <class T> int LB(vc<T> &a, T x){
        return int(lower_bound(all(a), x) - a.begin());
    }
    template <class T> int UB(vc<T> &a, T x){
        return int(upper_bound(all(a), x) - a.begin());
    }
    template <class T> T MAX(vc<T> &a, int l=0, int r=-1){
        if(r < 0) r = sz(a);
        return *max_element(a.begin()+l, a.begin()+r);
    }
    template <class T> T MIN(vc<T> &a, int l=0, int r=-1){
        if(r < 0) r = sz(a);
        return *min_element(a.begin()+l, a.begin()+r);
    }
    template <class T> auto vv(int d1, T x){
        return vc<T>(d1, x);
    }
    template <class T> auto vv(int d1, int d2, T x){
        return vc<vc<T>>(d1, vc<T>(d2, x));
    }
    template <class T> auto vv(int d1, int d2, int d3, T x){
        return vc<vc<vc<T>>>(d1, vv(d2, d3, x));
    }
    template <class T> auto vv(int d1, int d2, int d3, int d4, T x){
        return vc<vc<vc<vc<T>>>>(d1, vv(d2, d3, d4, x));
    }
    void outv(auto &v){
        for(auto &x: v) {cout<< x <<" ";} cout<<endl;
    }
    void rvec(int &n, auto &v){
        cin >> n; v.resize(n); for(auto &x: v) cin >> (x);
    }
    template<class T> istream& operator>> (istream& in, vector<T>& v) {
        lassert(!v.empty()); for(T &x: v) cin >> x;
        return in;
    }
    template <class Arg, class... Args>
    void read(Arg&& arg, Args&&... args){
        cin >> std::forward<Arg>(arg); using expander = int[];
        (void)expander{0, (void(cin >> std::forward<Args>(args)),0)...};
    }
    template <class Arg, class... Args>
    void out(Arg&& arg, Args&&... args){
        cout << std::forward<Arg>(arg); using expander = int[];
        (void)expander{0, (void(cout << " " << std::forward<Args>(args)),0)...};
        cout << endl;
    }
    template <class Integer, class F>
    Integer find_first_false(Integer l, Integer r, F&& f) {
        --l; // ++r;
        while (r - l > 1) {
            Integer m = midpoint(l, r);
            if (f(m)) l = m;
            else r = m;
        }
        return r;
    }
    template <class Integer, class F>
    Integer find_last_true(Integer l, Integer r, F &&f) {
        return find_first_false(l, r, [&f](Integer i) { return f(i); }) - 1;
    }
    template <class Integer, class F>
    Integer find_first_true(Integer l, Integer r, F &&f) {
        return find_first_false(l, r, [&f](Integer i) { return !f(i); });
    }
    template <class T, class F>
    T last_true(T lo, T hi, F&& f) { 
        lo--; // if all are false, return lo-1
        while(lo < hi){
            T mid = lo + (hi - lo + 1) / 2;
            if(f(mid)) lo = mid; 
            else hi = mid - 1;
        }
        return lo;
    }
    template <class T, class F>
    T first_true(T lo, T hi, F&& f) { 
        // return last_true(lo, hi, [&](T x){ return !f(x); }) + 1;
        hi++; // if all are false, return hi+1
        while(lo < hi){
            T mid = lo + (hi - lo) / 2;
            if(f(mid)) hi = mid; 
            else lo = mid + 1;
        }
        return lo;
    }

    ll pwr(ll base, ll p, ll mod){
        ll ans=1; while(p) {if(p&1) ans=(ans*base)%mod;
            base=(base*base)%mod; p/=2;}
        return ans;
    }
    ll gcd(ll a, ll b) {  return b == 0 ? a : gcd(b,a%b); }
    ll lcm(ll a, ll b) {  return a*(b/gcd(a,b)); }
    ll isqrt (ll x) {
        ll ans = sqrt(x)+2; while(ans*ans>x) ans--;
        return ans;
    }

    string yes(bool t = 1) { return t ? "YES" : "NO"; }
    string no(bool t = 1) { return yes(!t); }
    void pyes(bool t = 1) { out(yes(t)); }
    void pno(bool t = 1) { out(no(t)); }
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    const long double PI = (long double)(3.1415926535897932384626433832795);
    const ll  mx_ll   = numeric_limits<ll> :: max();
    const int mx_int  = numeric_limits<int> :: max();
    const int oo = 0x3f3f3f3f;
    const ll  OO = 0x3f3f3f3f3f3f3f3fll;
    const double eps = 1e-9;
    const int DX[8]={0,1, 0,-1,-1,1,-1, 1};
    const int DY[8]={1,0,-1, 0,-1,1, 1,-1};


bool MULTIPLE_TESTS = 0;
const int maxn = 1e5 + 3;
const int mod = 1e9+7;
void _build(){}

struct UnionFind { // OOP style
    int N; vi parent, siz; 
    UnionFind(int _N): N(_N) {
        siz.assign(N, 1);
        parent.assign(N, 0);
        for (int i = 0; i < N; i++) parent[i] = i;
    }
    int find(int i) {
        if(parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    bool same(int i, int j) { return find(i) == find(j); }
    void merge(int i, int j) {
        int a = find(i);
        int b = find(j);
        if (a != b) {
            if (siz[a] > siz[b]) swap(a, b);
            parent[a] = b;
            siz[b] += siz[a];
        }
    }
    int operator [] (int i) {
        return find(i);
    }
    int size(int x) {
        return siz[find(x)];
    }
    vvi gids(){
        vvi gs(N);
        forn(i, N) gs[find(i)].pb(i);
        return gs;
    }
    map<int, vi> groups(){ // for debug
        map<int, vi> groups;
        forn(i, N) groups[find(i)].pb(i);
        return groups;
    }
};

void _solve(){
    int n, m; cin >> n >> m;
    auto g = vv(n, m, '.'); cin >> g;
    auto d = vv(n, m, -1); 
    d[0][0] = 1;
    deque<pii> q; q.pb({0, 0});
    int ans = 0;
    while(!q.empty()){
        auto [x, y] = q.front(); q.pop_front();
        mmax(ans, d[x][y]);
        forn(k, 4){
            int nx = x + DX[k], ny = y + DY[k];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(g[nx][ny] == '.' or d[nx][ny] != -1) continue;
            if(g[x][y] == g[nx][ny]){
                d[nx][ny] = d[x][y];
                q.push_front({nx, ny});
            } else {
                d[nx][ny] = d[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
    }
    out(ans);
}


/*************************************************************************/

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //cout.precision(15);
    _build();
    int num_tests=1;
    if(MULTIPLE_TESTS) cin>>num_tests;
    if(MULTIPLE_TESTS) debug(num_tests);
    forn(i,num_tests){
        _solve();
    }
    // return 0;
    while(isspace(cin.peek())) cin.get();
    while(cin.peek() != EOF){
        _solve();
        while(isspace(cin.peek())) cin.get();
    }
}

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